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

1. הוכיחו כי NP EXP באמצעות הגדרת NP בעזרת מכונות הכרעה אי־דטרמיניסטיות. 2. הוכיחו כי NP PSPACE באמצעות הגדרת…

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

נוסח השאלה

  1. הוכיחו כי NP⊆EXPNP\subseteq EXP באמצעות הגדרת NPNP בעזרת מכונות הכרעה אי־דטרמיניסטיות.
  2. הוכיחו כי NP⊆PSPACENP\subseteq PSPACE באמצעות הגדרת NPNP בעזרת מכונות וידוא דטרמיניסטיות.

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

ייחוס מדויק

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

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

מטלה

2026 ב׳

2026ב_01_תרגיל_בית_1.md

שאלה 8עמוד 1נבדק אנושית
תרגול המשך

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

בחינהיהיו A ו- B שפות. ידוע ש- A ניתנת לרדוקציית זמן פולינומיאלי ל- B וש- A שלמה ל- EXP (ביחס לרדוקציות זמן פולינומיאלי). נתבונן בטענות הבאות: (i B ∈ NL. (…דומה בנושא — לא כפילותשיעור5. הוכיחו כי בעיית ההכרעה שמוגדרת להלן שייכת למחלקת הסיבוכיות P. קלט: גרף לא מכוון G = (V, E) ומספר טבעי k שאלה: האם קיימת קבוצה S V בגודל |S| = k עבו…דומה בנושא — לא כפילותבחינהנתונות מחלקות הסיבוכיות הבאות. I. המחלקה C 1 היא מחלקת כל השפות A Σ* עבור קיימת מכונת טיורינג אי-דטרמיניסטית M וקיימים c 1 כך שלכל x Σ*, אם x A אז קיי…דומה בנושא — לא כפילותבחינהנתונות מחלקות הסתביכויות הבאות. I. המחלקה C 1 היא כל השפות A Σ* עבורן קיימת מכונת טיורינג אי-דטרמיניסטית M וקיים c 1 כך שלכל x Σ*, אם x A אז כל ריצה ש…דומה בנושא — לא כפילותבחינהב. בעיית ההכרעה A מוגדרת כלהלן. קלט : נוסחה בוליאנית φ מצורת CNF שכל משתנה שלה מופיע בה 3 פעמים בדיוק (בצורת חיוב ו/או שלילה). שאלה : האם φ ספיקה? הוכ…דומה בנושא — לא כפילותבחינהנזכיר את בעיית הסוכן הנוסע. קלט: גרף לא מכוון שלם G = (V,E) עם משקלות w: E ℕ ומספר k ℕ. שאלה: האם קיים מעגל פשוט ב G העובר דרך כל הקודקודים ומשקלו לכל…דומה בנושא — לא כפילות

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