Complexity Atlas
HE
Source-backed question

עבור אילו מהטענות הבאות ידוע כי היא שקולה לטענה P = NP?

1Exams0Assignments0Lessons1Source documents
שאלת רב־ברירהq-2730eb4bb0a7

נוסח השאלה

עבור אילו מהטענות הבאות ידוע כי היא שקולה לטענה P = NP?
  1. אטענות ב' ג' נכונות.
  2. בקיים k ∈ N כך ש SAT ∈ DTime(n^k).
  3. גשפת כל הפלינדרומים מעל א"ב {0,1} היא NP-שלמה.
  4. דקיימת שפה Σ_2-שלמה.
  5. הטענות ב' ג' ו' נכונות.
  6. וקיים k ∈ N כך ש NP ⊆ DTime(n^k).

תמלול ראשון מתוך עמוד המקור ב־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 A

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

Question 7Page 7Visual reading

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

View source scan — page 7Source page 7 from נושא 131111 קבוצה 13111102 שנה 2023 סמסטר 2 מועד 1.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.

Assignment1. הוכיחו כי PSPACE סגורה תחת רדוקציות פולינומיות. 2. הוכיחו בשתי דרכים כי NP PSPACE: פעם אחת באמצעות ההגדרה הסטנדרטית ופעם אחת באמצעות הגדרת המוודא.…Topically related — not a duplicateAssignmentעבור כל אחת ממחלקות הסיבוכיות שלהלן, קבעו האם היא מכילה את המחלקה NP, האם NP מוכלת בה, והאם היא שווה לה, אם ידוע. אחרת הוכיחו כי השאלה שקולה לשאלה פתו…Topically related — not a duplicateAssignmentעבור כל אחת ממחלקות הסיבוכיות הבאות, קבעו אם היא מכילה את NP, מוכלת ב-NP, ושווה ל-NP - אם הדבר ידוע. הוכיחו את קביעותיכם. כאשר קובעים ששתי מחלקות שוות…Topically related — not a duplicateAssignmentעבור כל אחת מן המחלקות הבאות קבעו אם היא מכילה את NP, אם היא מוכלת ב-NP, ואם היא שווה ל-NP, ככל שידוע; אחרת הוכיחו כי השאלה שקולה לשאלה פתוחה. 1. C 1:…Topically related — not a duplicateAssignment1. יהי G=(V,E) גרף שאינו דווקא פשוט - ייתכנו בו קשתות מקבילות ולולאות - ויהי k מספר טבעי. נסמן ב-G' את הגרף הפשוט המתקבל מ-G באמצעות הוספת שני קודקודי…Topically related — not a duplicateAssignmentבכל סעיף מוצגות טענה ואלגוריתם. קבעו אם האלגוריתם מגדיר רדוקציית זמן פולינומי המוכיחה את הטענה, והוכיחו את קביעתכם. נשתמש בהגדרות: - נוסחת CNF ספיקה ב…Topically related — not a duplicate