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

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

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

נוסח השאלה

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

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

ייחוס מדויק

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

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

מטלה

2026 א׳

2026א_02_תרגיל_2.md

שאלה 5עמוד 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 העובר דרך כל הקודקודים ומשקלו לכל…דומה בנושא — לא כפילות

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