Complexity Atlas
HE
Source-backed question

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

0Exams1Assignments0Lessons1Source documents
שאלה פתוחהq-93c30dccbe91

נוסח השאלה

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

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

Exact provenance

Appearances by source document

Each card is a genuinely distinct file. Printed versions inside one PDF stay in that card and do not inflate the sitting count.

Assignment

2026 A

2026א_02_תרגיל_2.md

Question 5Page 1Human reviewed
Further practice

These are topic and lesson matches, not identical appearances.

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

Near variants — not duplicates