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

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

$$time_M(x)=O(f(|x|)), \qquad space_M(x)=O(g(|x|)).$$

1. הוכיחו כי לכל שתי פונקציות $f,g$: $$TISP^1(f,g)\subseteq DTime(f)\cap DSpace(g).$$ הסבירו מדוע הניסיון להוכיח את ההכלה בכיוון ההפוך נכשל.
2. הוכיחו:
   1. לכל פונקציה $f$: $$TISP^1(f,f)=DTime(f).$$
   2. לכל פונקציה $f$: $$DSpace(f)\subseteq TISP^1(2^{O(f)},f).$$
   3. לכל שתי פונקציות $f,g$: $$TISP^6(f,g)\subseteq TISP^1(f\cdot g,g).$$