Complexity Atlas
HE
Source-backed question

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

1Exams0Assignments0Lessons1Source documents
שאלת רב־ברירה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. צילום העמוד מצורף למטה כדי שאפשר יהיה לאמת סימון מתמטי וניסוח.

Exact provenance

Appearances by source document

Each card is a genuinely distinct file. Printed versions inside one PDF stay in that card and do not inflate the sitting count.

Exam

2023 B · moed B

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

Question 2Page 2Visual reading

Byte-identical aliases: נושא 131111 קבוצה 13111103 שנה 2023 סמסטר 2 מועד 2.pdf · נושא 131111 קבוצה 13111104 שנה 2023 סמסטר 2 מועד 2.pdf · נושא 131111 קבוצה 13111105 שנה 2023 סמסטר 2 מועד 2.pdf

View source scan — page 2Source page 2 from נושא 131111 קבוצה 13111102 שנה 2023 סמסטר 2 מועד 2.pdf Open full size

The pages this was written from

1 page

These pages were chosen by word overlap between the text here and the page's transcription — nobody has verified them. Treat them as a lead to check, not a citation.

Further practice

These are topic and lesson matches, not identical appearances.

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

Near variants — not duplicates