It is known
- $P \subset P/poly$
- $NP \not\subset P/poly \Rightarrow P \neq NP$
However, do we have a proof of: $P \neq NP \Rightarrow NP \not\subset P/poly$ ?
I.e. is there a world where $P \neq NP$, but $NP \subset P/poly$?
Thanks!
MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up.
Sign up to join this communityIt is known
However, do we have a proof of: $P \neq NP \Rightarrow NP \not\subset P/poly$ ?
I.e. is there a world where $P \neq NP$, but $NP \subset P/poly$?
Thanks!
No, it is unknown whether $P \neq NP \Rightarrow NP \not\subset P/Poly$. However, one may show that if $NP \subset P/Poly$ then the polynomial hierarchy collapses on the second level, what is rather unlikely.
There are oracles relative to which $P\neq NP$ but $NP\subseteq P/poly$.