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

1. הוכיחו כי רדוקציות זמן פולינומי מקיימות טרנזיטיביות. כלומר, לכל A,B,C *, אם A p B וגם B p C, אז A p C. 2. ה…

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

נוסח השאלה

  1. הוכיחו כי רדוקציות זמן פולינומי מקיימות טרנזיטיביות. כלומר, לכל A,B,C⊆Σ∗A,B,C\subseteq\Sigma^*, אם A≤pBA\le_p B וגם B≤pCB\le_p C, אז A≤pCA\le_p C.
  2. הוכיחו כי EXPEXP סגורה לרדוקציות זמן פולינומי.
  3. הוכיחו כי NPSPACENPSPACE סגורה לרדוקציות זמן פולינומי.

נוסח מטלה שנבדק אנושית.

ייחוס מדויק

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

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

מטלה

2026 א׳

2026א_03_תרגיל_3.md

שאלה 1עמוד 1נבדק אנושית

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

3 עמודים

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

תרגול המשך

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

בחינהלהזכירכם מהכרטיע לקלט הבעיה Subset-Sum הוא S קבוצת מספרים ו-t סכום יעד (כולל בייצוג בינארי) והשאלה היא האם קיימת תמית קבוצה חלקית S' של S שסכומה t. לפ…דומה בנושא — לא כפילותבחינהמבין המחלקות הבאות, מה המחלקה הקטנה ביותר ביחס להכלה שידוע לגביה שהיא סגורה תחת רדוקציות זמן פולינומיאלי.דומה בנושא — לא כפילותבחינהיהיו A ו- B שפות. ידוע ש- A ניתנת לרדוקציית זמן פולינומיאלי ל- B וש- A שלמה ל- EXP (ביחס לרדוקציות זמן פולינומיאלי). נתבונן בטענות הבאות: (i B ∈ NL. (…דומה בנושא — לא כפילותבחינהנתאר להלן רדוקציה מ- 3-SAT ל- IS (תזכורת: IS היא שפת הזוגות <G,k> של גרף ומספר k כך שבגרף G יש קבוצה בלתי תלויה בגודל k). הרדוקציה: בהינתן קידוד של נו…דומה בנושא — לא כפילותבחינהנתאר להלן רדוקציה מ- 3-SAT ל- IS (תזכורת: IS היא שפת הזוגות <G,k> של גרף G ומספר k כך שבגרף G יש קבוצה בלתי תלויה בגודל k). הרדוקציה: בהינתן קידוד של…דומה בנושא — לא כפילותבחינהבהוכחת משפט קוק-לוין יצאנו משפה B NP והראינו שהיא ניתנת לרדוקציית זמן פולינומיאלי ל- SAT. לשם כך, עבור קלט x לשפה B נעזרנו בטבלה ריבועית T M,x בגודל q…דומה בנושא — לא כפילות