Skip to main content

It is known (1) P \subset P/poly (2) "NP \not\subset P/poly" --> "P \neq NP"

  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" --> "NP \not\subset P/poly"$P \neq NP \Rightarrow NP \not\subset P/poly$ ?

I.e. is there a world where P \neq NP$P \neq NP$, but NP \subset P/poly$NP \subset P/poly$?

Thanks!

It is known (1) P \subset P/poly (2) "NP \not\subset P/poly" --> "P \neq NP"

However, do we have a proof of: "P \neq NP" --> "NP \not\subset P/poly" ?

I.e. is there a world where P \neq NP, but NP \subset P/poly?

Thanks!

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!

Source Link
LowerBounds
  • 663
  • 8
  • 22

"P vs NP" and "NP vs P/Poly"

It is known (1) P \subset P/poly (2) "NP \not\subset P/poly" --> "P \neq NP"

However, do we have a proof of: "P \neq NP" --> "NP \not\subset P/poly" ?

I.e. is there a world where P \neq NP, but NP \subset P/poly?

Thanks!