It is known


1. $P \subset P/poly$
2. $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!



"P vs NP" and "NP vs P/Poly"
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.


