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

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