SU-CS254B APR212025

NP-Intermediate If P = NP, then no distinction between P and NP, but…
If \text{P} \neq \text{NP}, then exists “NP-intermediate” problem such that L \in \text{NP} such that L \not \in P and L is not NP-complete.
But today, we will prove a weaker’s version.
Ladner’s Theorem Weaker’s Ladner’s theorem:
Assuming \text{SAT} requires 2^{\Omega\left(n\right)}, then there are NP-intermediate languages.
PadSAT Consider:

\begin{equation} \text{PadSAT}_{m} = \left\{\langle \varphi, 1^{m} \rangle : \varphi \in \text{SAT}\right\} \end{equation}

This is easier than SAT since you have a bigger n artificially, and you can throw away the m.
Proof idea Choose m appropriately so that PadSAT falls in the sweet spot between P and NP complete. In particular, we choose:

\begin{equation} \text{PadSAT} = \left\{ \langle \varphi, 1^{2^{\sqrt{|\varphi|}}} \rangle, \phi \in \text{SAT}\right\} \end{equation}

Meaning, N = n+2^{\sqrt{n}}}=2^{\theta\left(\sqrt{n}\right)}.
We show three things:
PadSAT is in NP (witness is just the satisfying assignment) PadSAT not in P PadSAT is not NP-Complete PadSAT not in P PadSAT is not in P
Assume for contradiction PadSAT is in P, meaning \exists algorithm in polytime that decides PadSAT in poly(N) time; there is an 2^{\theta\left(\sqrt{n}\right)} time algorithm for SAT.
pad the input to length using 2^{\theta\left(\sqrt{n}\right)} time solve using the oracle, which takes at most 2^{\theta\left(\sqrt{n}\right)} time note that this contradicts our assumption that SAT is in 2^{\Omega\left(n\right)}.
PadSAT is not NP-Complete PadSAT is not NP complete
Suppose for the sake of contradiction that PadSAT is NP-complete. We will see that \text{SAT} \leq_{P} \text{PadSAT}, which contradictions the assumption.
Consider: \Phi \stackrel{?}{\in} \text{SAT} with N = |\Phi| where, after a Poly(N) reduction, we have \langle \varphi, 1^{2^{\sqrt{|\phi|}}} \rangle where \Phi \in \text{SAT} \Leftrightarrow \varphi \in \text{SAT} by the assumption.
Now, consider what |\varphi| = n is in terms of N:
n + 2^{\sqrt{n}} = \text{poly}\left(N\right) IFF 2^{\theta \left(\sqrt{n}\right)} = \text{poly} \left(N\right) IFF \theta \left(\sqrt{N}\right) = \theta \left(\log N\right) IFF n = \theta \left(\log^{2} N\right) this is compression! Meaning, we can run an extraction procedure