Suggest edit — SU-CS254B APR212025

Title

Name

Note

---
title: "SU-CS254B APR212025"
source: https://www.jemoka.com/posts/kbhsu_cs254b_apr212025/
date: 2025-04-21
---

NP-Intermediate If \(P = NP\), then no distinction between \(P\) and \(NP\), but&hellip;
If \(\text{P} \neq \text{NP}\), then exists &ldquo;NP-intermediate&rdquo; 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&rsquo;s version.
Ladner&rsquo;s Theorem Weaker&rsquo;s Ladner&rsquo;s theorem:
Assuming \(\text{SAT}\) requires \(2^{\Omega\qty(n)}\), then there are NP-intermediate languages.
PadSAT Consider:
\begin{equation} \text{PadSAT}_{m} = \qty {\langle \varphi, 1^{m} \rangle : \varphi \in \text{SAT}} \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} = \qty { \langle \varphi, 1^{2^{\sqrt{|\varphi|}}} \rangle, \phi \in \text{SAT}} \end{equation}
Meaning, \(N = n+2^{\sqrt{n}}}=2^{\theta\qty(\sqrt{n})}\).
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\qty(\sqrt{n})}\) time algorithm for SAT.
pad the input to length using \(2^{\theta\qty(\sqrt{n})}\) time solve using the oracle, which takes at most \(2^{\theta\qty(\sqrt{n})}\) time note that this contradicts our assumption that SAT is in \(2^{\Omega\qty(n)}\).
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}\qty(N)\) IFF \(2^{\theta \qty(\sqrt{n})} = \text{poly} \qty(N)\) IFF \(\theta \qty(\sqrt{N}) = \theta \qty(\log N)\) IFF \(n = \theta \qty(\log^{2} N)\) this is compression! Meaning, we can run an extraction procedure