Suggest edit — SU-CS254B APR142025

Title

Name

Note

---
title: "SU-CS254B APR142025"
source: https://www.jemoka.com/posts/kbhsu_cs254b_apr142025/
date: 2025-04-14
---

Some motivations time and space are usually considered as independent resources but now&hellip; 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 &ldquo;ingredients&rdquo; (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&rsquo;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&hellip;.
$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 )$.