Complexity Atlas
HE
Source-backed question

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

0Exams1Assignments0Lessons1Source documents
שאלה פתוחהq-5c95d5445a2e

נוסח השאלה

  1. הוכיחו כי EXPEXP סגורה לרדוקציות זמן פולינומי.
  2. הוכיחו כי 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 B

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

Question 4Page 1Human reviewed

The pages this was written from

3 pages

These pages were chosen by word overlap between the text here and the page's transcription — nobody has verified them. Treat them as a lead to check, not a citation.

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 duplicateExamמבין המחלקות הבאות, מה המחלקה הקטנה ביותר ביחס להכלה שידוע לגביה שהיא סגורה תחת רדוקציות זמן פולינומיאלי.Topically related — not a duplicateExamלהזכירכם מהכרטיע לקלט הבעיה Subset-Sum הוא S קבוצת מספרים ו-t סכום יעד (כולל בייצוג בינארי) והשאלה היא האם קיימת תמית קבוצה חלקית S' של S שסכומה t. לפ…Topically related — not a duplicateExamב. בעיית ההכרעה A מוגדרת כלהלן. קלט : נוסחה בוליאנית φ מצורת CNF שכל משתנה שלה מופיע בה 3 פעמים בדיוק (בצורת חיוב ו/או שלילה). שאלה : האם φ ספיקה? הוכ…Topically related — not a duplicateExamבהוכחת משפט קוק-לוין יצאנו משפה B NP והראינו שהיא ניתנת לרדוקציית זמן פולינומיאלי ל- SAT. לשם כך, עבור קלט x לשפה B נעזרנו בטבלה ריבועית T M,x בגודל q…Topically related — not a duplicateExamנזכיר את בעיית הסוכן הנוסע. קלט: גרף לא מכוון שלם G = (V,E) עם משקלות w: E ℕ ומספר k ℕ. שאלה: האם קיים מעגל פשוט ב G העובר דרך כל הקודקודים ומשקלו לכל…Topically related — not a duplicate