רדוקציות סיבוכיות
רדוקציות מיפוי בזמן פולינומיאלי. אלו מעבירות קושי: אם A ≤p B ו־A קשה, גם B קשה. זהו הכלי המשמש להוכחת NP-שלמות.
HAMPATH ≤p HAMCYCLE
רדוקציה בזמן פולינומיאלי ממסלול המילטוני למעגל המילטוני.
HAMCYCLE ≤p HAMPATH
הכיוון ההפוך: רדוקציה ממעגל המילטוני למסלול המילטוני על ידי שכפול צומת אחד.
INDEPENDENT-SET ≤p CLIQUE
קחו את הגרף המשלים: קבוצות בלתי־תלויות ב־G מתאימות לקליקות ב־G̅.
CLIQUE ≤p INDEPENDENT-SET
הכיוון ההפוך באמצעות אותה בנייה של גרף משלים.
בקש עוד
חסר משהו? צור קשר ונוסיף אותו.