בעיית ההכרעה Partition מוגדרת כלהלן. קלט : רשימת מספרים טבעיים (a 1, a 2, , a n) נתונים בייצוג עשרוני. שאלה :…

בעיית ההכרעה Partition מוגדרת כלהלן. קלט : רשימת מספרים טבעיים $(a_1, a_2, \ldots, a_n)$ נתונים בייצוג עשרוני. שאלה : האם קיימת קבוצה $I \subseteq {1,2, \ldots, n}$ עבורה מתקיים $Σ_{j\in I} a_j = Σ_{j\notin I} a_j$ ? בעיית ההכרעה Special-Cut מוגדרת כלהלן. קלט : גרף פשוט לא מכוון G. שאלה : האם קיים בגרף G חתך (S, S̄) בגודל 0 המקיים |S| = |S̄| ? (תזכורת : חתך בגודל 0 הוא חתך שאף קשת של הגרף אינה חוצה.) נגדיר פונקציה f שמתאימה לכל רשימת מספרים טבעיים $(a_1, a_2, \ldots, a_n)$ גרף G שכולל n קליקים בגדלים $a_1, a_2, \ldots, a_n$ ללא קשתות בין קודקודים של קליקים שונים. (תזכורת : קליק בגרף הוא קבוצת קודקודים, שכל שניים שונים מביניהם מחוברים בקשת.) לכל אחת מהטענות שלהלן, קבעו האם היא נכונה, אינה נכונה, או שקולה לשאלה פתוחה. א. טענה : הפונקציה f היא רדוקציה מהבעיה Partition לבעיה Special-Cut. הטענה נכונה / אינה נכונה / שקולה לשאלה פתוחה (הקיפו בחירתכם) ב. טענה : קיימת מכונת טיורינג שמחשבת את הפונקציה f בזמן פולינומיאלי. הטענה נכונה / אינה נכונה / שקולה לשאלה פתוחה (הקיפו בחירתכם) 2