Perspective
All Votes
Loading Discussion
P = NP? Are polynomial time solvable problems as difficult as problems whose answer can be verified in polynomial time? P vs. NP problem in wikipedia

There exist many claimed proofs of P=NP. One of those could be correct.

Fagin's theorem: NP is equivalent in expressive power to existential second order logic. P is equivalent to first order logic with a least fixed point operation.Descriptive complexity theory in wikipedia.

NP describes complexity class of feasible concurrent computation. P describes complexity class of feasible sequential computation.

The P=NP question is a good source of jokes

Most computer scientists believe P != NP.

P=NP is an important unsolved problem in computer science.

There exist many claimed proofs of P!=NP. One of these could be correct.

Current methods are probably insufficient to decide P=NP.

The P=NP problem is likely to be undecidable.

P=NP could be dependent on another difficult problem, such as the Fermat's last theorem.

It's likely that concepts in P=NP problem description have been misunderstood. Official problem description from Clay mathematics institute