Some motivations
- time and space are usually considered as independent resources
- but now… consider them as joint (dependent) resources!
question!: what are simultaneous time and space efficient systems? Our interest: time space trade-offs.
Time-Space Tradeoffs
Consider the case that a single TM does something time and space efficiently.
\begin{equation} \text{TISP}\qty(t\qty(n), s \qty(n)) = \qty {L: \exists \text{TM that decides $L$ in time $O(t(n))$, and space $O\qty(s \qty(n))$}} \end{equation}
Some theorems
No algorithm that solves SAT in \(O\qty(n)\) time and \(O\qty(\log n)\) space simultaneously. That is, \(\text{SAT} \not \in \text{TISP}\qty(n, \log n)\).
We have three competingly high lower bound:
\begin{align} \text{SAT} \not \in \text{TISP} \qty(n^{\sqrt{2}}, n^{o\qty(1)}) \end{align}
where \(n^{o\qty(1)} \approx n^{0.00000001}\). This is followed up by:
\begin{equation} \text{SAT}\not \in \text{TISP}\qty(n^{\phi = 1.618}, n^{o\qty(1)}) \end{equation}
finally, using computed aided search, we have:
\begin{equation} \text{SAT}\not \in \text{TISP}\qty(n^{2 \cos \qty(\frac{\pi}{7})}, n^{o\qty(1)}) \end{equation}
In fact, this is optimal. We have a barrier result!
\(n^{1.8}\) is optimal among all possible compos of the “ingredients” (TODO define later) we will see.
SAT is complete for n poly log n
Rather than SAT, we will prove an equivalent statement about:
\begin{equation} \text{NTIME}\qty(n \text{poly} \log n) \not \subseteq \text{TIMP}\qty(n^{c}, n^{o\qty(1)}) \end{equation}
This is because:
\(\text{SAT}\) is complete for \(\text{NTIME}\qty( n \text{poly} \log n)\)
The proof for this is essentially just a souped up version of Cook-Levin Theorem. To prove this, we need Quasi-Linear Cook-Levin. In fact, we will even prove a harder thing:
\begin{equation} \text{NTIME}\qty(n) \not \in \text{TISP}\qty(n^{c}, n^{o\qty(1)}) \end{equation}
Let’s get started
Proof
We need two ingredients we will need.
Time hierarchy theorems for \(\Sigma_{k}\) and \(\pi_{k}\)
This is the same proof as the regular time hierarchy theorem.
\begin{equation} \text{TIME}\qty(o\qty(t\qty(n))) \not \subseteq \Sigma_{k} \text{TIME}\qty(t\qty(n)) \end{equation}
ditto for \(\pi_{k}\). We are going to assume this for now.
TISP speed-ups by adding quantifiers
\begin{equation} \text{TISP}\qty(t,s) \subseteq \Sigma_{2} \text{TIME}\qty(\sqrt{t} \sqrt{s}) \text{ if } s \geq \log n \end{equation}
Let \(L \in \text{TISP}\qty(t\qty(n), \sqrt{n})\), and \(M\) be corresponding \(TM\).
The configuration of \(M\) on input \(x\) at time \(l\) will give you everything you need; this tableau includes….
- \(O\qty(s)\) worktape contents
- \(O\qty(\log s)\) worktape heads
- \(O\qty(\log n)\) input tape head
- \(O\qty(1)\) state
in total this is going to be \(O\qty(s)\).
Shown: \(L \in \Sigma_{2} \text{TIME}\qty( \frac{t}{r} s + \log \qty(\frac{t}{r}) tr)\). In particular the thing in the parentheses gives \(O\qty( \frac{t}{r} s + r )\).