נגדיר TISP(f,g) כמחלקת השפות הניתנות להכרעה על ידי מכונת טיורינג סטנדרטית בעלת סרט יחיד בזמן O(f(n)) ובזיכרון…

נגדיר $TISP(f,g)$ כמחלקת השפות הניתנות להכרעה על ידי מכונת טיורינג סטנדרטית בעלת סרט יחיד בזמן $O(f(n))$ ובזיכרון $O(g(n))$.

1. קבעו איזו מן המחלקות $$TISP(f,g), \qquad DTime(f)\cap DSpace(g)$$ מוכלת באחרת. הסבירו מדוע הכיוון ההפוך אינו נובע מן ההגדרות.
2. הוכיחו או הפריכו: $$TISP(n^3,n^3)=DTime(n^3).$$