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

  • 2
    $\begingroup$ 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? $\endgroup$ – Tom van der Zanden Apr 18 '15 at 21:25
  • $\begingroup$ Why does "$\hat{\Pi}$ is in P" follow "from hypothesis of $\:$NP $\subseteq$ P/poly$\:$" $\;\;$ ? $\;\;\;\;\;\;$ $\endgroup$ – user12859 Apr 19 '15 at 2:44
  • $\begingroup$ because of constants chosen. see sdcvcc answer below. $\endgroup$ – Turbo Apr 19 '15 at 2:46
  • 2
    $\begingroup$ @RickyDemer Please stop manually spacing your answers and comments. They look unreadably terrible on everybody's screen but yours. $\endgroup$ – David Richerby Apr 19 '15 at 8:57
  • $\begingroup$ 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. $\endgroup$ – David Richerby 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).

  • $\begingroup$ 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}$. $\endgroup$ – Turbo Apr 19 '15 at 2:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.