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})$ באמצעות מוודא ועד באורך אקספוננציאלי.

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

ייחוס מדויק

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

מטלה

2025_02_תרגיל_2.md

שאלה 2עמוד 1נבדק אנושית