3 ms·

http://en.wikipedia.org/wiki/P_versus_NP_problem#Consequences_of_proof http://en.wikipedia.org/wiki/P_versus_NP_problem#Consequence...

• DanielRibeiro 16y ago
  This kinda covers it, but it would also mean that BPP = NP. This is because P != NP => BPP = P (which is equivalent to BPP != P => P = NP, which is a fancy way of saying that at least one of {BPP, NP} is P). Since BPP (http://en.wikipedia.org/wiki/BPP http://en.wikipedia.org/wiki/BPP) essentially encompasses problems that can be solved with very high probability chance in polynomial time (the definition requires probability only higher than 50%, but you can iterate a polynomial amount of time, and reach probability arbitrary close to 1), it is expected that BPP = P. Not to mention that the huge amount of derandomization techniques are more evidence that this is very likely to be true.
• deleted 16y ago
  [deleted]