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

1. הוכיחו כי EXP סגורה לרדוקציות זמן פולינומי. 2. הוכיחו כי NP סגורה לרדוקציות זמן פולינומי.

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

נוסח השאלה

  1. הוכיחו כי EXPEXP סגורה לרדוקציות זמן פולינומי.
  2. הוכיחו כי NPNP סגורה לרדוקציות זמן פולינומי.

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

ייחוס מדויק

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

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

מטלה

2026 ב׳

2026ב_02_תרגיל_בית_2.md

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

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

3 עמודים

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

תרגול המשך

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

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