SU-CS254B APR142025 — Jemoka Knowledge Base

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}\left(t\left(n\right), s \left(n\right)\right) = \left\{L: \exists \text{TM that decides $L$ in time $O(t(n))$, and space $O\left(s \left(n\right)\right)$}\right\} \end{equation}

Some theorems No algorithm that solves SAT in O\left(n\right) time and O\left(\log n\right) space simultaneously. That is, \text{SAT} \not \in \text{TISP}\left(n, \log n\right). We have three competingly high lower bound:

\begin{align} \text{SAT} \not \in \text{TISP} \left(n^{\sqrt{2}}, n^{o\left(1\right)}\right) \end{align}

where n^{o\left(1\right)} \approx n^{0.00000001}. This is followed up by:

\begin{equation} \text{SAT}\not \in \text{TISP}\left(n^{\phi = 1.618}, n^{o\left(1\right)}\right) \end{equation}

finally, using computed aided search, we have:

\begin{equation} \text{SAT}\not \in \text{TISP}\left(n^{2 \cos \left(\frac{\pi}{7}\right)}, n^{o\left(1\right)}\right) \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}\left(n \text{poly} \log n\right) \not \subseteq \text{TIMP}\left(n^{c}, n^{o\left(1\right)}\right) \end{equation}

This is because: \text{SAT} is complete for \text{NTIME}\left( n \text{poly} \log n\right) 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}\left(n\right) \not \in \text{TISP}\left(n^{c}, n^{o\left(1\right)}\right) \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}\left(o\left(t\left(n\right)\right)\right) \not \subseteq \Sigma_{k} \text{TIME}\left(t\left(n\right)\right) \end{equation}

ditto for \pi_{k}. We are going to assume this for now. TISP speed-ups by adding quantifiers

\begin{equation} \text{TISP}\left(t,s\right) \subseteq \Sigma_{2} \text{TIME}\left(\sqrt{t} \sqrt{s}\right) \text{ if } s \geq \log n \end{equation}

Let L \in \text{TISP}\left(t\left(n\right), \sqrt{n}\right), 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\left(s\right) worktape contents O\left(\log s\right) worktape heads O\left(\log n\right) input tape head O\left(1\right) state in total this is going to be O\left(s\right). Shown: L \in \Sigma_{2} \text{TIME}\left( \frac{t}{r} s + \log \left(\frac{t}{r}\right) tr\right). In particular the thing in the parentheses gives O\left( \frac{t}{r} s + r \right).