Idea behind $\mathsf{NP}\subseteq\mathsf{P}/\mathsf{Poly}\implies\mathsf{P}=\mathsf{NP}$ not true? - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-09-15T20:34:48Z https://cs.stackexchange.com/feeds/question/41549 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/41549 1 Idea behind $\mathsf{NP}\subseteq\mathsf{P}/\mathsf{Poly}\implies\mathsf{P}=\mathsf{NP}$ not true? T.... https://cs.stackexchange.com/users/9753 2015-04-18T20:40:00Z 2015-04-19T09:13:35Z <p>$\mathsf{3SAT}$ in $n$ variables is an $\mathsf{NP}$ complete problem.</p> <p>Augment input to $\mathsf{3SAT}$ with constants $\{a_i\}_{i=1}^{n^c}$ where each constant $|a_i|&lt;n^e$ to get an artificial problem ${\mathsf{3SAT}}_{aug}$. There is a direct reduction from $\mathsf{3SAT}$ to ${\mathsf{3SAT}}_{aug}$.</p> <p>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.</p> <p>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.</p> <p><strong>${\mathsf{3SAT}}_{aug}$ is $\mathsf{NP}-\mathsf{complete}$:</strong> $\mbox{ }$ Since $\mathsf{3SAT}$ reduces to ${\mathsf{3SAT}}_{aug}$, ${\mathsf{3SAT}}_{aug}$ problem remain $\mathsf{NP}-\mathsf{complete}$.</p> <p><strong>${\mathsf{3SAT}}_{aug}$ is in $\mathsf{P}$:</strong> $\mbox{ }$ Follows from hypothesis of $\mathsf{NP}\subseteq \mathsf{P}/\mathsf{Poly}$.</p> <p>So why then is still $\mathsf{NP}\subseteq\mathsf{P}/\mathsf{Poly}\implies\mathsf{P}=\mathsf{NP}$ not true?</p> https://cs.stackexchange.com/questions/41549/-/41553#41553 6 Answer by sdcvvc for Idea behind $\mathsf{NP}\subseteq\mathsf{P}/\mathsf{Poly}\implies\mathsf{P}=\mathsf{NP}$ not true? sdcvvc https://cs.stackexchange.com/users/667 2015-04-18T22:05:07Z 2015-04-18T22:05:07Z <p>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$ (<a href="http://Assume%20$%5Cmathsf%7BNP%7D%5Csubseteq%20%5Cmathsf%7BP%7D/%5Cmathsf%7BPoly%7D$.%20Let%20$%5CPi$%20be%20a%20NP-complete%20problem,%20by%20assumption,%20this%20problem%20can%20be%20solved%20by%20some%20circuit%20family.%20It%20is%20true%20that%20the%20problem%20$%5Chat%7B%5CPi%7D$%20where%20the%20input%20is%20a%20pair%20consisting%20of%20input%20to%20$%5CPi$%20and%20a%20circuit%20making%20an%20appropriate%20computation,%20is%20in%20$%5Cmathsf%7BP%7D$.%20However,%20from%20this%20fact%20you%20cannot%20conclude%20that%20the%20original%20problem%20$%5CPi$%20is%20in%20$%5Cmathsf%7BP%7D$.%20To%20obtain%20a%20solution%20to%20$%5CPi$%20you%20have%20to%20guess%20the%20circuit%20-%20and%20this%20is%20not%20a%20priori%20possible%20in%20$%5Cmathsf%7BP%7D$.%20You%20could%20guess%20the%20circuit%20nondeterministically,%20but%20then%20the%20argument%20would%20prove%20that%20$%5Cmathsf%7BNP%7D%20=%20%5Cmathsf%7BNP%7D$.%20However,%20if%20you%20start%20with%20a%20$%5CSigma_2$%20set%20instead,%20it%20is%20possible%20to%20fix%20this%20reasoning%20and%20obtain%20$%5CSigma_2=%5CPi_2$%20(http://en.wikipedia.org/wiki/Karp%E2%80%93Lipton_theorem).">Karp-Lipton theorem</a>).</p> https://cs.stackexchange.com/questions/41549/-/41561#41561 2 Answer by Tom van der Zanden for Idea behind $\mathsf{NP}\subseteq\mathsf{P}/\mathsf{Poly}\implies\mathsf{P}=\mathsf{NP}$ not true? Tom van der Zanden https://cs.stackexchange.com/users/1100 2015-04-19T07:37:44Z 2015-04-19T09:13:35Z <blockquote> <p>Since $\mathsf{3SAT}$ reduces to ${\mathsf{3SAT}}_{aug}$, ${\mathsf{3SAT}}_{aug}$ problem remain $\mathsf{NP}-\mathsf{complete}$.</p> </blockquote> <p>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.</p>