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

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

$$time_M(x)\le c\cdot f(|x|) \qquad\text{וגם}\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.$$