Kialo requires cookies to work correctly.
P = NP?
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 1974]: 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.
Technical problem shoud not be decided with public debate but with technical proofs.
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
Is Linux the best operating system?
Is computer science a failing discipline?
Do we exist within a Simulated Reality?