../

2026-09-23 Scribe

$\newcommand{\PH}{\mathbf{PH}}$ $\newcommand{\P}{\mathbf{P}}$ $\newcommand{\NP}{\mathbf{NP}}$ $\newcommand{\coNP}{\mathbf{coNP}}$ $\newcommand{\NPC}{\mathbf{NP-complete}}$ $\newcommand{\SPACE}{\mathbf{SPACE}}$ $\newcommand{\PSPACE}{\mathbf{PSPACE}}$ $\newcommand{\NSPACE}{\mathbf{NSPACE}}$ $\newcommand{\L}{\mathbf{L}}$ $\newcommand{\coNL}{\mathbf{coNL}}$ $\newcommand{\NL}{\mathbf{NL}}$

$\newcommand{\SAT}{\mathsf{SAT}}$ $\newcommand{\TSAT}{\mathsf{3SAT}}$ $\newcommand{\TQBF}{\mathsf{SAT}}$ $\newcommand{\PATH}{\mathsf{PATH}}$ $\newcommand{\INDSET}{\mathsf{INDSET}}$ $\newcommand{\EINDSET}{\mathsf{EXACT}\ \mathsf{INDSET}}$ $\newcommand{\MED}{\mathsf{MIN-EQ-DNF}}$

Presentation - Karp Lipton theorem

Theorem 1: Theorem

If $\NP \subseteq \P/_{poly}$ then $\PH = \Sigma_2^p$

Polynomial Hierarchy

Motivation

$\INDSET$

We have seen that certain problem capture the “essence” of a complexity class.

  • $\SAT$ captures the essence of $\P$ and $\NP$
  • $\TQBF$ captures the essence of $\SPACE$ ($\PSPACE$ and $\NSPACE$ are equivalent according to Savitch’s theorem
  • $\PATH$ is $\NL\textbf{-complete}$

Now think about this problem $\INDSET = \{\langle G, k\rangle:\text{ graph } G\text{ has an independent set of size }\ge k\}$

$\INDSET \in \NP$ and $\INDSET \in \NPC$

The proof for this is pretty straightforward. The witness $w$ is the set itself and you can check that its size is less than $k$ in polynomial time. The set itself is sure to be polynomial in the input length. Hence it is in $\NP$.

$\TSAT$ is reducible to $\INDSET$. $\SAT$ is reducible to $\TSAT$. $\forall L \in \NP \le_p \SAT$. Hence $\INDSET$ is $\NPC$

Consider a slight modification to this problem

$\EINDSET = \{\langle G, k\rangle :\text{ the largest independent set has size }k\}$

The proof for this is not so short, at least not at first sight. Finding an independent set of size $k$ seems the same as $\INDSET$, but how do we prove that it is smaller than all other independent sets.

In other words $\exists$ some independent set $x^$ such that $\forall$ other independent sets $x$, $x^ \ge x$

$\MED$

Consider the following problem of $\MED = \{ \langle \varphi, k\rangle: \exists\text{ equivalent DNF formula of size }\le k\}$

DNF is not did-not-finish. It is a disjunction of conjunctions. It is Disjunctive Normal Form

This is circuit minimization stated as a decision problem

Think about the negation of this:

$\overline{\MED} = \{ \langle \varphi, k \rangle :\not{\exists}\text{ No equivalent DNF formula of size }\le k\}$

In other words, $\forall\psi$ DNF formula of size $\le k$, $\exists u$ such that $\varphi(u) \ne \psi(u)$

Do you notice the pattern? There are two quantifiers.

We saw that $\NP$ is all about finding $\exists$ and $\coNP$ is all about $\forall$

Now we have combinations of them. Polynomial hierarchy generalizes these.