[[
wikihub
]]
Search
⌘K
Explore
People
For Agents
Sign in
Explore
People
For Agents
Sign in
@jemoka / Jemoka Knowledge Base / raw/course/cs254b/kbhsu_cs254b_apr142025.md
Suggest edit
Cancel
Submit suggestion
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… 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 )\).