Part 1 Relativization Barrier to P vs. NP: \exists oracles A such that P^{A} = NP^{A}, Space and Time: \text{TIME}\left(t\right) \subseteq \text{SPACE}\left(\frac{t\left(n\right)}{\log \left(t\left(n\right)\right)} \right) pebbling game (constant degree digraph, can only place if pebble adjacent): can be pebbled with \leq O\left( \frac{v}{\log v}\right) pebbles Time Space Constraints: \text{SAT} \not \in \text{TISP}\left(n^{1.8}, n^{o\left(1\right)}\right), 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\left(n\right)} circuits, then \text{P} = \text{BPP}. if you have an average-case hard problem, you can get a pseudo-random generator \left(H^{*}\right) — 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 Beyond Worst-Case Beyond Worst-Case Analysis