נסתכל על 3 הבעיות הבאות: בעיית ההכרעה של SAT: בהינתן נוסחה בוליאנית בצורת CNF – האם הנוסחה…

שאלת רב־ברירהq-0c98c8761251

נוסח השאלה

נסתכל על 3 הבעיות הבאות: בעיית ההכרעה של SAT: בהינתן נוסחה בוליאנית בצורת CNF – האם הנוסחה ספיקה. בעיית החיפוש של SAT: בהינתן נוסחה בוליאנית בצורת CNF – למצוא השמה מספקת אם יש כזו או להודיע "לא" אם אין לנוסחה השמה מספקת. בעיית האופטימיזציה של SAT: בהינתן נוסחה בוליאנית בצורת CNF – מה המספר המקסימלי של פסוקיות שניתן לספק (על ידי איזושהי השמה). מה הטענה הנכונה (כאשר בכל המקרים הכוונה במילה "פתרון" היא על ידי מכונת טיורינג דטרמיניסטית)?

אאם ניתן לפתור בזמן פולינומיאלי אפילו אחת משלוש הבעיות אז NP = P.
בידוע שניתן לפתור אחת מהבעיות בזמן פולינומיאלי אך לא ידוע אם ניתן לפתור את שתי האחרות בזמן
גידוע שניתן לפתור שתיים מהבעיות בזמן פולינומיאלי אך לא ידוע אם ניתן לפתור את הבעיה הנוספת בזמן פולינומיאלי.
דידוע שניתן לפתור את שלוש הבעיות בזמן פולינומיאלי.
הידוע שניתן לפתור בזמן פולינומיאלי את הבעיה המשלימה לבעיית ההכרעה של SAT.
ועבור לפחות אחת מ- 3 הבעיות לא ידוע שאם ניתן לפתור אותה בזמן פולינומיאלי אז NP = P.