Part 1
- Relativization Barrier to P vs. NP: \(\exists\) oracles \(A\) such that \(P^{A} = NP^{A}\),
- Space and Time: \(\text{TIME}\qty(t) \subseteq \text{SPACE}\qty(\frac{t\qty(n)}{\log \qty(t\qty(n))} )\)
- pebbling game (constant degree digraph, can only place if pebble adjacent): can be pebbled with \(\leq O\qty( \frac{v}{\log v})\) pebbles
- Time Space Constraints:
- \(\text{SAT} \not \in \text{TISP}\qty(n^{1.8}, n^{o\qty(1)})\), no one machine can do both
- Ladner’s Theorem: assuming P != NP, there are NP-intermediate languages
Part 2
Hardness vs. Randomness
If SAT requires \(2^{\Omega\qty(n)}\) circuits, then \(\text{P} = \text{BPP}\).
- if you have an average-case hard problem, you can get a pseudo-random generator \(\qty(H^{*})\) — Probabilistic Random Generator
- PRG generation from randomness
- Yao’s Next-Bit Prediction Lemma
- combinatorial designs (for input size distributions)
hardness amplification:
- worts-case hardness => average case hardness
Frontier
- beyond worst-case analysis
- hardness within P
- undirected STCONN and expanded graphs