SU-CS254B APR142025
Last edited: August 8, 2025Some 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)\).
SU-CS254B APR212025
Last edited: August 8, 2025NP-Intermediate
If \(P = NP\), then no distinction between \(P\) and \(NP\), but…
If \(\text{P} \neq \text{NP}\), then exists “NP-intermediate” problem such that \(L \in \text{NP}\) such that \(L \not \in P\) and \(L\) is not NP-complete.
But today, we will prove a weaker’s version.
Ladner’s Theorem
Weaker’s Ladner’s theorem:
Assuming \(\text{SAT}\) requires \(2^{\Omega\qty(n)}\), then there are NP-intermediate languages.
PadSAT
Consider:
\begin{equation} \text{PadSAT}_{m} = \qty {\langle \varphi, 1^{m} \rangle : \varphi \in \text{SAT}} \end{equation}
SU-CS254B APR302025
Last edited: August 8, 2025H*: there’s a language \(A\) such that…
- \(A \in \text{TIME}\qty(2^{O\qty(n)})\)
- \(\exists \delta >0\) such that if \(C_{n}\) is a n-var circuit of size \(\leq 2^{\delta n}\) we have \(\text{Pr}\qty[ C_{n}\qty(x) = A_{n}\qty(x)] \leq \frac{1}{2} + 2^{-\delta n}\)
stretching randomness
Goal: take \(S \sim \qty {\pm 1}^{l}\), we want to stretch this randomness \(\qty {\pm 1}^{n}\) where \(n = 2^{\theta\qty(l)}, l = \theta \qty(\log n)\).
Two main parts:
- combinatorial designs
- Yao’s Next-Bit Prediction Lemma
We can choose sufficiently small \(l\), in particular to be \(l = c \log n\), because then we can iterate over all seeds in time \(2^{l} = n^{c}\).
SU-CS254B MAR312025
Last edited: August 8, 2025A Tour Through 254B’s Complexity Theory
Chapter 1: No School like the Old School
6 lectures, 4 theorems from the 70s.
the *relavitization barrier" to P vs. NP
Diagonalization is doomed to fail at resolving P vs. NP
what has diagonalization proved?
It shows a lot of impossibilities (“x can’t be applied to y”)
- Cantor’s theorem
- Godel’s incompleteness
- halting problem
- time/space hierarchy theorems
Hopcroft-Paul-Valiant
“On space versus time”
SU-CS254B MAY052025
Last edited: August 8, 2025\begin{equation} H^{*} \implies \text{PRG} G \qty {\pm 1}^{l} \to \qty {\pm 1}^{n} \end{equation}
where \(L = O\qty(\log n)\) that 0/1 fools circuits of size \(n^{3}\).
which ultimately shows P = BPP.