מחלקות סיבוכיות
מקרא
P, NP, NP-שלם, NP-קשה
NP-קשה הוא כל מה שכל בעיה ב־NP ניתנת לרדוקציה אליו בזמן פולינומיאלי — הוא משתרע מעבר ל־NP אל מחלקות קשות יותר. NP-שלם הוא החפיפה: בעיות NP-קשות שהן עצמן עדיין ב־NP.
עולם האפשרויות
היחסים בין P, NP ו־coNP אינם מוכרעים. כל דיאגרמה להלן מתארת טופולוגיה העקבית עם כל הידוע כיום — הוכחה או הפרכה של אחת מהן תפתור אחת מהשאלות הפתוחות המרכזיות בתורת הסיבוכיות.
P ⊊ NP ∩ coNPמשוער כרגע
ההשערה המקובלת. בעיות כמו FACTORING ו־GRAPH-ISO משוערות לחיות ב־NP ∩ coNP אך מחוץ ל־P.
P = NPפתוח
כל שלוש המחלקות קורסות לאחת. P = NP מכריח אוטומטית NP = coNP, שכן P סגורה תחת משלים.
NP = coNP, P ⊊ NPפתוח
NP סגורה תחת משלים, אך אימות עדיין קל ממש מהכרעה.
P = NP ∩ coNPפתוח
NP ו־coNP שונות, אך כל בעיה בשתיהן כבר נמצאת ב־P. לא קיימות בעיות "ביניים".