1. הוכיחו כי המחלקות הבאות סגורות לרדוקציות זמן פולינומיאלי: 1. PSPACE. 2. c 1DTime(n n c). 2. תהא B=\0\ שפה ה…

1. הוכיחו כי המחלקות הבאות סגורות לרדוקציות זמן פולינומיאלי:
   1. $PSPACE$.
   2. $\displaystyle\bigcup_{c\ge1}DTime(n^{n^c})$.
2. תהא $B=\{0\}$ שפה המכילה מחרוזת אחת בלבד.
   1. הוכיחו כי לכל $A\in P$ מתקיים $A\le_p B$.
   2. הוכיחו כי $DTime(n^{2024})$ אינה סגורה לרדוקציות זמן פולינומיאלי.

הדרכה: השתמשו בסעיף הקודם ובמשפט היררכיית הזמן.