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

Question

$\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?

Answer 1

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.

Answer 2

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).