---
title: "SU-CS254B MAR312025"
source: https://www.jemoka.com/posts/kbhsu_cs254b_mar312025/
date: 2025-03-31
---

A Tour Through 254B&rsquo;s Complexity Theory Chapter 1: No School like the Old School 6 lectures, 4 theorems from the 70s.
the *relavitization barrier&quot; to P vs. NP Diagonalization is doomed to fail at resolving P vs. NP
what has diagonalization proved?
It shows a lot of impossibilities (&ldquo;x can&rsquo;t be applied to y&rdquo;)
Cantor&rsquo;s theorem Godel&rsquo;s incompleteness halting problem time/space hierarchy theorems Hopcroft-Paul-Valiant &ldquo;On space versus time&rdquo;
\begin{equation} \text{TIME}\qty(t\qty(n)) \subseteq \text{SPACE}\qty(\frac{t}{\log t}) \end{equation}
meaning, in particular,
\begin{equation} \text{TIME}\qty(t\qty(n)) \subset \text{SPACE}\qty(t\qty(n)) \end{equation}
so upper-bounding space complexity with time complexity is actually strict! We will do this using a &ldquo;pebble game&rdquo; reduction.
Time-Space Tradeoffs So far been studying time and space as separate resources; we ask: is there any tension between using time or space.
&ldquo;if you want to be very time/space efficient your space/time explodes!&rdquo;
Ladner&rsquo;s Theorem on &ldquo;NP-intermediate Problems&rdquo; Two important types of problems in NP:
easy: those in \(P\) hard: those that are NP-complete If P != NP, then there exists a non-NP complete NP problem.
Chapter 2: The Big Surprise 20 years&rsquo; worth of one theorem&mdash;the hardness vs. randomness paradigm. &ldquo;Hardness is in tension with randomness.&rdquo;
&ldquo;If SAT is hard then randomness is useless.&rdquo; Formally:
If SAT requires exponential size circuits, then P = BPP.
ingredients &ldquo;pesudorandom generators&rdquo; (PRGs) and derandomization to prove P = BPP, it suffices to design good PRGs average-case hardness gives good PRGs worst-case hardness can be made harder to average case harder (&ldquo;hardness amplification&rdquo;) Chapter 3: The Research Frontier beyond worst-case analysis typically, the standard definition of &ldquo;solving a task&rdquo; must be able to handle all possible instances, but we may be able to relax this.
constant factors: we may be able to find a &ldquo;goodish&rdquo; solution; for instance, solving sat in \(1.8^{n}\) is far better than \(2^{n}\) average case: we can change &ldquo;for all&rdquo; to &ldquo;for most&rdquo;, so we don&rsquo;t solve all of a problem but a distribution subpart of it approximate: we can change the acceptance criteria to be weaker (for SAT, for instance, we perhaps can relax it such that we only subset of clauses is satisfied) hardness within P So far, we think of all polynomial operations in P as &ldquo;efficient.&rdquo; \(n^{3}\), in reality, isn&rsquo;t that efficient. Often times, with large \(n\), even \(n^{2}\) is too slow.
dynamic programming problems
Longest Common Subsequence &mdash; whether or not there exists a possibly-not-continuous subsequence of an input sequence. Big open problem: does there exist an \(O\qty(n^{1.99})\) time algorithm.
We&rsquo;ll see connections of this task to the P vs. NP problem! This is quite surprising. We can show the connection with \(O\qty(n^{1.99})\) and P vs. NP with a reduction!
