Complexity Atlas
HE
Source-backed question

1. הוכיחו כי רדוקציות זמן פולינומי מקיימות טרנזיטיביות. כלומר, לכל A,B,C *, אם A p B וגם B p C, אז A p C. 2. ה…

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

נוסח השאלה

  1. הוכיחו כי רדוקציות זמן פולינומי מקיימות טרנזיטיביות. כלומר, לכל A,B,C⊆Σ∗A,B,C\subseteq\Sigma^*, אם A≤pBA\le_p B וגם B≤pCB\le_p C, אז A≤pCA\le_p C.
  2. הוכיחו כי EXPEXP סגורה לרדוקציות זמן פולינומי.
  3. הוכיחו כי NPSPACENPSPACE סגורה לרדוקציות זמן פולינומי.

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

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א_03_תרגיל_3.md

Question 1Page 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להזכירכם מהכרטיע לקלט הבעיה Subset-Sum הוא S קבוצת מספרים ו-t סכום יעד (כולל בייצוג בינארי) והשאלה היא האם קיימת תמית קבוצה חלקית S' של S שסכומה t. לפ…Topically related — not a duplicateExamמבין המחלקות הבאות, מה המחלקה הקטנה ביותר ביחס להכלה שידוע לגביה שהיא סגורה תחת רדוקציות זמן פולינומיאלי.Topically related — not a duplicateExamיהיו A ו- B שפות. ידוע ש- A ניתנת לרדוקציית זמן פולינומיאלי ל- B וש- A שלמה ל- EXP (ביחס לרדוקציות זמן פולינומיאלי). נתבונן בטענות הבאות: (i B ∈ NL. (…Topically related — not a duplicateExamנתאר להלן רדוקציה מ- 3-SAT ל- IS (תזכורת: IS היא שפת הזוגות <G,k> של גרף ומספר k כך שבגרף G יש קבוצה בלתי תלויה בגודל k). הרדוקציה: בהינתן קידוד של נו…Topically related — not a duplicateExamנתאר להלן רדוקציה מ- 3-SAT ל- IS (תזכורת: IS היא שפת הזוגות <G,k> של גרף G ומספר k כך שבגרף G יש קבוצה בלתי תלויה בגודל k). הרדוקציה: בהינתן קידוד של…Topically related — not a duplicateExamבהוכחת משפט קוק-לוין יצאנו משפה B NP והראינו שהיא ניתנת לרדוקציית זמן פולינומיאלי ל- SAT. לשם כך, עבור קלט x לשפה B נעזרנו בטבלה ריבועית T M,x בגודל q…Topically related — not a duplicate