מפת הסיבוכיות
EN
שאלה מבוססת מקור

אילו מסדרות ההכלה הבאות ידוע כנכונה ?

1בחינות0מטלות0שיעורים1מסמכי מקור
שאלת רב־ברירהq-59fa9f0dba63

נוסח השאלה

אילו מסדרות ההכלה הבאות ידוע כנכונה ?
  1. אcoNP⊆Σ_2⊆PSPACE⊆EXP.
  2. בcoNP⊆Σ_2⊆EXP⊆PSPACE.
  3. גEXP⊆coNP⊆Σ_2⊆PSPACE.
  4. דΣ_2⊆EXP⊆coNP⊆PSPACE.
  5. הEXP⊆PSPACE⊆coNP⊆Σ_2.
  6. וcoNP⊆PSPACE⊆Σ_2⊆EXP.

תמלול ראשון מתוך עמוד המקור ב־tools/summary/.work. צילום העמוד מצורף למטה כדי שאפשר יהיה לאמת סימון מתמטי וניסוח.

ייחוס מדויק

מופעים לפי מסמך מקור

כל כרטיס הוא קובץ שונה באמת. גרסאות או שאלונים כפולים באותו PDF מוצגים בתוך אותו כרטיס ואינם מגדילים את מספר המועדים.

בחינה

2023 ב׳ · מועד ב׳

נושא 131111 קבוצה 13111102 שנה 2023 סמסטר 2 מועד 2.pdf

שאלה 2עמוד 2קריאה חזותית

עותקים זהים של אותו מסמך: נושא 131111 קבוצה 13111103 שנה 2023 סמסטר 2 מועד 2.pdf · נושא 131111 קבוצה 13111104 שנה 2023 סמסטר 2 מועד 2.pdf · נושא 131111 קבוצה 13111105 שנה 2023 סמסטר 2 מועד 2.pdf

הצגת צילום המקור — עמוד 2עמוד מקור 2 מתוך נושא 131111 קבוצה 13111102 שנה 2023 סמסטר 2 מועד 2.pdf פתיחה בגודל מלא

העמודים שמהם זה נכתב

1 עמודים

העמודים נבחרו לפי חפיפת מילים בין הטקסט כאן לתמלול העמוד — לא אומתו ידנית. הם הצעה לבדיקה, לא ציטוט.

תרגול המשך

אלו התאמות לפי נושא ושיעור — לא מופעים זהים של אותה שאלה.

מטלהעבור כל אחת ממחלקות הסיבוכיות שלהלן, קבעו האם היא מכילה את המחלקה NP, האם NP מוכלת בה, והאם היא שווה לה, אם ידוע. אחרת הוכיחו כי השאלה שקולה לשאלה פתו…דומה בנושא — לא כפילותמטלהלכל אחת מבעיות ההכרעה שלהלן קבעו מהי מחלקת הסיבוכיות הקטנה ביותר ביחס להכלה שאליה ידוע שהיא שייכת מבין המחלקות P,NP,coNP,EXP. הוכיחו את קביעותיכם. 1.…דומה בנושא — לא כפילותמטלהעבור כל אחת ממחלקות הסיבוכיות הבאות, קבעו אם היא מכילה את NP, מוכלת ב-NP, ושווה ל-NP - אם הדבר ידוע. הוכיחו את קביעותיכם. כאשר קובעים ששתי מחלקות שוות…דומה בנושא — לא כפילותשיעור5. הוכיחו כי בעיית ההכרעה שמוגדרת להלן שייכת למחלקת הסיבוכיות P. קלט: גרף לא מכוון G = (V, E) ומספר טבעי k שאלה: האם קיימת קבוצה S V בגודל |S| = k עבו…דומה בנושא — לא כפילותמטלהבשאלה זו נוכיח כי בעיית Bin-Packing שראינו בשיעור היא NP-שלמה. הקלט הוא סדרת מספרים a 1,a 2, ,a n (0,1] ומספר טבעי k. השאלה היא האם ניתן לחלק את המספר…דומה בנושא — לא כפילותמטלההוכיחו כי השפות 3NAE ו-IS הן NP-שלמות.דומה בנושא — לא כפילות

וריאציות קרובות — לא כפילויות