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

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

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

נוסח השאלה

מבין המחלקות הבאות, מה המחלקה הקטנה ביותר ביחס להכלה שידוע לגביה שהיא סגורה תחת רדוקציות זמן פולינומיאלי.
  1. אNP.
  2. בPSPACE.
  3. גL.
  4. דNL.
  5. הDSpace(log^2 n).
  6. וEXP.

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

ייחוס מדויק

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

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

בחינה

2024 א׳ · מועד ב׳

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

שאלה 4עמוד 3קריאה חזותית
הצגת צילום המקור — עמוד 3עמוד מקור 3 מתוך נושא 131111 קבוצה 13111101 שנה 2024 סמסטר 1 מועד 2.pdf פתיחה בגודל מלא

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

1 עמודים

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

תרגול המשך

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

מטלה1. הוכיחו כי PSPACE סגורה תחת רדוקציות פולינומיות. 2. הוכיחו בשתי דרכים כי NP PSPACE: פעם אחת באמצעות ההגדרה הסטנדרטית ופעם אחת באמצעות הגדרת המוודא.…דומה בנושא — לא כפילותמטלה1. הוכיחו כי המחלקות הבאות סגורות לרדוקציות זמן פולינומיאלי: 1. PSPACE. 2. c 1DTime(n n c). 2. תהא B=\0\ שפה המכילה מחרוזת אחת בלבד. 1. הוכיחו כי לכל…דומה בנושא — לא כפילותמטלהלכל טענה קבעו האם היא נכונה, אינה נכונה, או שקולה לשאלה פתוחה, והוכיחו את קביעתכם. השפה SAT-UNSAT היא שפת הזוגות ( 1, 2) של נוסחאות בוליאניות מצורת CN…דומה בנושא — לא כפילותמטלה1. הוכיחו כי RP NP. 2. הוכיחו כי BPP PSPACE. 3. הוכיחו כי מחלקת הסיבוכיות RP סגורה לחיתוך, כלומר שאם A,B RP אז A B RP. 4. זהו את מחלקות הסיבוכיות שלהל…דומה בנושא — לא כפילותמטלהעבור כל אחת מן המחלקות הבאות קבעו אם היא מכילה את NP, אם היא מוכלת ב-NP, ואם היא שווה ל-NP, ככל שידוע; אחרת הוכיחו כי השאלה שקולה לשאלה פתוחה. 1. C 1:…דומה בנושא — לא כפילותמטלה1. הוכיחו כי רדוקציות זמן פולינומי מקיימות טרנזיטיביות. כלומר, לכל A,B,C *, אם A p B וגם B p C, אז A p C. 2. הוכיחו כי EXP סגורה לרדוקציות זמן פולינומ…דומה בנושא — לא כפילות

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