World's most popular travel blog for travel bloggers.

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

, ,
Problem Detail:

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

#### Answered By : Tom van der Zanden

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.