Skip to main content
5 of 7
replaced http://stackoverflow.com/ with https://stackoverflow.com/

#$P=NP$

Let me tick the list:

  1. Most likely false, because, as Scott Aaronson said "If $P = NP$, then the world would be a profoundly different place than we usually assume it to be."

  2. Yes, it's The Open Problem in computational complexity theory

  3. Yes, it's old

  4. It's important, again quoting Scott: "because if it would be true, there would be no special value in "creative leaps," no fundamental gap between solving a problem and recognizing the solution once it's found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss..."

  5. It's an equality rather than a negation

Carlo Beenakker
  • 209.2k
  • 19
  • 517
  • 745