הבדלים בין גרסאות בדף "סיבוכיות"

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

תפריט ניווט