1. הוכיחו כי PSPACE סגורה תחת רדוקציות פולינומיות. 2. הוכיחו בשתי דרכים כי NP PSPACE: פעם…

שאלה פתוחהq-bf0ddf0ac5c7

נוסח השאלה

הוכיחו כי $PSPACE$ סגורה תחת רדוקציות פולינומיות.
הוכיחו בשתי דרכים כי $NP\subseteq PSPACE$ : פעם אחת באמצעות ההגדרה הסטנדרטית ופעם אחת באמצעות הגדרת המוודא. מותר להשתמש בשוויון $PSPACE=NPSPACE$ . הסיקו כי $NP\subseteq EXP$ .
הוכיחו כי השפה $\left\{\langle M,x,0^t\rangle\ \middle|\ M \text{ מקבלת את }x\text{ וגם }space_M(x)\le t\right\}$ שייכת ל- $PSPACE$ .
הוכיחו את האפיון השקול הבא של $NEXP=\bigcup_{c\ge1}NTime(2^{n^c})$ באמצעות מוודא ועד באורך אקספוננציאלי.

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

Exact provenance

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

Assignment

2025_02_תרגיל_2.md

Question 2Page 1Human reviewed