6
$\begingroup$

Many people have tried to solve the very famous problem "P vs NP" and a lot of solutions are proposed. (e.g. A. D. Plotnikov, On the Relationship between Classes P and NP). But I couldn't find any reputable place to find out if these solutions are right or not, and if not why not? How can I know the answer? Is the problem solved? By whom? how?

Thanks in advance.

p.s. A set of possible solutions could be found at http://www.win.tue.nl/~gwoegi/P-versus-NP.htm but I couldn't find out if they are correct or not.

$\endgroup$
7
  • 14
    $\begingroup$ No, it's not. Otherwise I'm sure you would have heard about it. $\endgroup$
    – Alex Provost
    Commented May 3, 2013 at 21:19
  • $\begingroup$ @AlexP. something I have been wondering but don't think it merits its own question... is the P vs NP question itself an NP problem? $\endgroup$
    – tacos_tacos_tacos
    Commented May 3, 2013 at 21:20
  • 6
    $\begingroup$ @tacos: actually it's solvable in constant time (there exists a program that prints the solution: either the program which prints "yes" or the program which prints "no"). (It's not a problem in the same sense that a problem admitting a polynomial-time algorithm is a problem; in particular, it doesn't take an input.) $\endgroup$
    – Qiaochu Yuan
    Commented May 3, 2013 at 21:21
  • 2
    $\begingroup$ @tacos: as far as I know, yes (but recall that there is a difference between "decidable" as it is used in logic and "decidable" as it is used in computability theory and here I mean the former). Scott Aaronson has written about this: see scottaaronson.com/papers/pnp.pdf . $\endgroup$
    – Qiaochu Yuan
    Commented May 3, 2013 at 21:30
  • 1
    $\begingroup$ @Shayan : it is such an important problem that if anyone proved it and its proof survived the scrutiny of experts, the news would even make the popular press and you would hear about it without trying. It is one of the "Clay Millenium Problems" (? not sure about the exact name) and there is a one million dollar bounty for whoever solves it. $\endgroup$
    – Stefan Smith
    Commented May 4, 2013 at 1:56

1 Answer 1

Reset to default
16
$\begingroup$

It is currently unknown whether $P = NP$. All purported proofs have either

  • been shown to be faulty,
  • are under review, or
  • are dismissed by the community at large without being considered.

For more information on the last one, you might want to read Scott Aaronson's blog post detailing indicators why a purported proof is likely to be wrong and won't receive much attention.

Hope this helps!

$\endgroup$
2
  • $\begingroup$ translate.google.com/… $\endgroup$
    – Xander
    Commented Jan 29, 2014 at 0:37
  • $\begingroup$ @Xander That, too, is not an accepted proof. It would be all over the news, everywhere, if an actual accepted proof were found. $\endgroup$
    – Caleb Stanford
    Commented May 8, 2015 at 6:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .