Co-NP
co-NP הוא אוסף בעיות שהן ההפך של הבעיות ב־NP. NP הן בעיות שיש להן הוכחה קצרה שאפשר לבדוק מהר. זמן פולינומי הוא זמן חישוב סביר. דוגמה פשוטה: יש קבוצה של מספרים. שואלים אם יש תת־קבוצה שסכומה אפס. אם כן, נותנים את הרשימה ובודקים את הסכום. ההפך שואל האם אין בכלל תת־קבוצה שסכומה אפס. גם לזה יש הוכחה שני...
ההיררכיה הפולינומית
ההיררכיה הפולינומית היא דרך לסדר בעיות קשות לפי רמות. היא כוללת קבוצות כמו P, NP ו-co-NP. אורקל זה כלי מדומה. מכונה יכולה לשאול אותו שאלה ולקבל תשובה מיד. זה עוזר להגדיר יכולות חזקות יותר. כמתים הם מילים לוגיות. "קיים" אומר שיש משהו. "לכל" אומר שכולם מקיימים תנאי. הדרגה הראשונה היא P. כל דרגה חדשה...