Suggest edit — SU-CS254B MAY142025

Title

Name

Note

---
title: "SU-CS254B MAY142025"
source: https://www.jemoka.com/posts/kbhsu_cs254b_may142025/
date: 2025-05-14
---

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&rsquo;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^{*})\) &mdash; Probabilistic Random Generator PRG generation from randomness Yao&rsquo;s Next-Bit Prediction Lemma combinatorial designs (for input size distributions) hardness amplification:
worts-case hardness =&gt; average case hardness Frontier beyond worst-case analysis hardness within P undirected STCONN and expanded graphs Beyond Worst-Case Beyond Worst-Case Analysis