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.
SU-CS254B MAY072025
Last edited: August 8, 2025hardcore lemma
Goal: can we find a single set of \(x \in \qty {\pm 1}^{h} = H\) where \(|H| \geq \frac{\delta}{2}\), such that for \(f : \qty {\pm 1 }^{h} \to \qty {\pm 1}\), for all circuits of size \(S\), commuting \(f\) on inputs in \(H\) is hopelessly hard (i.e., the \(\mathbb{Pr}_{x \in H} \qty [f\qty(x) =c\qty(x)] \leq \frac{1}{2} + \frac{\varepsilon}{2} \implies \mathbb{E}_{x \sim H} \qty [f\qty(x) c\qty(x)] \leq \varepsilon\).