# Idea behind $\mathsf{NP}\subseteq\mathsf{P}/\mathsf{Poly}\implies\mathsf{P}=\mathsf{NP}$ not true?

$\mathsf{3SAT}$ in $n$ variables is an $\mathsf{NP}$ complete problem.

Augment input to $\mathsf{3SAT}$ with constants $\{a_i\}_{i=1}^{n^c}$ where each constant $|a_i|<n^e$ to get an artificial problem ${\mathsf{3SAT}}_{aug}$. There is a direct reduction from $\mathsf{3SAT}$ to ${\mathsf{3SAT}}_{aug}$.

Assume that $\mathsf{NP}\subseteq \mathsf{P}/\mathsf{Poly}$ where suppose there exists $n^c$ constants for a fixed $c$ that will help solve any $n$-variate $\mathsf{3SAT}$ instance in $n^d$ time for a fixed $d$, however finding those constants offline takes exponential amount of time.

Since by hypothesis of $\mathsf{NP}\subseteq \mathsf{P}/\mathsf{Poly}$, we have constants that help solve $\mathsf{3SAT}$ in poly time, let augmented input to ${\mathsf{3SAT}}_{aug}$ contain constants that help solve ${\mathsf{3SAT}}_{aug}$ in poly time.

${\mathsf{3SAT}}_{aug}$ is $\mathsf{NP}-\mathsf{complete}$: $\mbox{ }$ Since $\mathsf{3SAT}$ reduces to ${\mathsf{3SAT}}_{aug}$, ${\mathsf{3SAT}}_{aug}$ problem remain $\mathsf{NP}-\mathsf{complete}$.

${\mathsf{3SAT}}_{aug}$ is in $\mathsf{P}$: $\mbox{ }$ Follows from hypothesis of $\mathsf{NP}\subseteq \mathsf{P}/\mathsf{Poly}$.

So why then is still $\mathsf{NP}\subseteq\mathsf{P}/\mathsf{Poly}\implies\mathsf{P}=\mathsf{NP}$ not true?

• What exactly does it mean to augment $\Pi$ with constants? What do you mean by "let augmented input [...] contain these constants"? Why can you just assume/claim that the input contains those constants? Apr 18 '15 at 21:25
• Why does "$\hat{\Pi}$ is in P" follow "from hypothesis of $\:$NP $\subseteq$ P/poly$\:$" $\;\;$ ? $\;\;\;\;\;\;$
– user12859
Apr 19 '15 at 2:44
• because of constants chosen. see sdcvcc answer below.
– Mr.
Apr 19 '15 at 2:46
• Please define the problem $\overline{\mathsf{3SAT}}$. And please use some other notation for it: over-line normally denotes complement, so $\overline{\mathsf{3SAT}}$ normally denotes the set of unsatisfiable 3CNF formulae. Apr 19 '15 at 9:00
Since $\mathsf{3SAT}$ reduces to ${\mathsf{3SAT}}_{aug}$, ${\mathsf{3SAT}}_{aug}$ problem remain $\mathsf{NP}-\mathsf{complete}$.
The "reduction" isn't a polynomial time one. To create an input for ${\mathsf{3SAT}}_{aug}$ you need to compute the constants $\{a_i\}$ which takes exponential time.
Assume $\mathsf{NP}\subseteq \mathsf{P}/\mathsf{Poly}$. Let $\Pi$ be a NP-complete problem, by assumption, this problem can be solved by some circuit family. It is true that the problem $\hat{\Pi}$ where the input is a pair consisting of input to $\Pi$ and a circuit making an appropriate computation, is in $\mathsf{P}$. However, from this fact you cannot conclude that the original problem $\Pi$ is in $\mathsf{P}$. To obtain a solution to $\Pi$ using $\hat{\Pi}$ you have to guess the circuit - and this is not a priori possible in $\mathsf{P}$. You could guess the circuit nondeterministically, but then the argument would prove that $\mathsf{NP} = \mathsf{NP}$. However, if you start with a $\Sigma_2$ set instead, it is possible to fix this reasoning and obtain $\Sigma_2=\Pi_2$ (Karp-Lipton theorem).
• Since $\mathsf{3SAT}$ reduces to $\Pi$ which reduces to $\hat{\Pi}$, doesn't $\hat{\Pi}$ problem remain $\mathsf{NP}-\mathsf{complete}$? By definition $\hat{\Pi}\in\mathsf{NP}$, while since $\mathsf{3SAT}$ reduces to $\hat{\Pi}$ every problem in $\mathsf{NP}$ reduces to $\mathsf{3SAT}$ $\implies$ every problem in $\mathsf{NP}$ reduces to $\hat{\Pi}$.