תורת הסיבוכיות – הבדלי גרסאות

תורת הסיבוכיות מבחינה לעתים קרובות בין התשובה "כן" לתשובה "לא". דוגמה: הקבוצה [[NP (סיבוכיות)|NP]] היא קבוצת הבעיות שבהן התשובה "כן" ניתנת לבדיקה בזמן סביר. הקבוצה [[Co-NP]] היא קבוצת הבעיות שבהן התשובה "לא" ניתנת לבדיקה בזמן סביר. הקידומת Co היא קיצורה של המלה complement - משלים. המשלים של בעיה נתונה היא הבעיה שבה כל התשובות "כן" ו"לא" מוחלפות זו בזו. הבעיה "האם ראשוני" והבעיה "האם פריק" (מספר פריק הוא מספר שאינו ראשוני) משלימות זו את זו.

 

 

הקבוצה [[P (סיבוכיות)|P]] היא קבוצת כל בעיות ההכרעה שניתן לפתור אותן באמצעות [[מכונת טיורינג|מכונה דטרמיניסטית]] ב[[זמן ריצה פולינומי|זמן פולינומי]]. הקבוצה [[NP (סיבוכיות)|NP]] היא קבוצת כל בעיות ההכרעה שניתן לפתור אותן באמצעות [[מכונת טיורינג לא-דטרמיניסטית|מכונה לא דטרמיניסטית]] ב[[זמן ריצה פולינומי|זמן פולינומי]], או - לחליפין - לבדוק נכונות של פתרון נתון ב[[זמן ריצה פולינומי|זמן פולינומי]]. השאלה "האם הקבוצה [[P (סיבוכיות)|P]] שווה לקבוצה [[NP (סיבוכיות)|NP]]" היא השאלה המרכזית במדעי המחשב. זו שאלה פתוחה, [[מכון קליי למתמטיקה]] מציע פרס של מיליון דולר לראשון שיפתור אותה.