שאלה מבוססת מקור

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

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

ייחוס מדויק

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

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

בחינה

2023 ב׳ · מועד א׳

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

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

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

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