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:

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:

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