עבור f,g: N N נגדיר את TISP(f,g) כמחלקת השפות A * שעבורן קיימת מכונת טיורינג M בעלת אלפבית קלט וקיימים קבועים…

עבור $f,g:\mathbb N\to\mathbb N$ נגדיר את $TISP(f,g)$ כמחלקת השפות $A\subseteq\Sigma^*$ שעבורן קיימת מכונת טיורינג $M$ בעלת אלפבית קלט $\Sigma$ וקיימים קבועים $c,d>0$, כך ש-$M$ מכריעה את $A$ ולכל $x\in\Sigma^*$,

$$time_M(x)\le c\cdot f(|x|), \qquad space_M(x)\le d\cdot g(|x|).$$

1. הוכיחו או הפריכו: לכל $f$ מתקיים $TISP(f,f)=DTime(f)$.
2. הוכיחו כי $$TISP(f,g)\subseteq DTime(f)\cap DSpace(g).$$ נסו להבין לעצמכם, לא להגשה, מדוע הניסיון להוכיח הכלה בכיוון ההפוך נכשל.
3. האם הטענה הבאה נכונה, אינה נכונה או שקולה לשאלה פתוחה? $$\bigcup_{c\ge1}TISP(n^c,n^c)=PSPACE.$$