רדוקציות סיבוכיות

רדוקציות מיפוי בזמן פולינומיאלי. אלו מעבירות קושי: אם A ≤p B ו־A קשה, גם B קשה. זהו הכלי המשמש להוכחת NP-שלמות.

רדוקציה בזמן פולינומיאלי ממסלול המילטוני למעגל המילטוני.

הכיוון ההפוך: רדוקציה ממעגל המילטוני למסלול המילטוני על ידי שכפול צומת אחד.

קחו את הגרף המשלים: קבוצות בלתי־תלויות ב־G מתאימות לקליקות ב־G̅.

הכיוון ההפוך באמצעות אותה בנייה של גרף משלים.