תוצאה של Ryan Williams קובעת כי לכל פונקציה f: N N המקיימת n f(n),

תוצאה של Ryan Williams קובעת כי לכל פונקציה $f:\mathbb N\to\mathbb N$ המקיימת $n\le f(n)$,

$$DTime(f)\subseteq DSpace\left(\sqrt f\cdot\log_2 f\right).$$

1. הראו כי $$DTime(2^n)\subseteq DSpace(2^{0.51n}).$$
2. נניח שלכל $\varepsilon>0$ ולכל $f$ המקיימת $n\le f(n)$ מתקיים $$DTime(f)\subseteq DSpace(f^\varepsilon).$$ הוכיחו כי $P\ne PSPACE$.