Open Questions
Does P equal NP?
Citation Formats
General Reference
APA Style
BibTeX
Open Question
The P versus NP problem asks whether every problem whose solution can be quickly checked can also be quickly solved. It has resisted proof or disproof since it was formalized in the early 1970s and is one of the seven Millennium Prize Problems; a solution in either direction would reshape cryptography, optimization and much of theoretical computer science.
What would resolve this A rigorous proof that P equals NP, exhibiting a general fast algorithm for an NP-complete problem, or a proof that P does not equal NP, most likely by establishing a genuine computational barrier no such algorithm can cross.
OpenTheoretical computer science and mathematical logicMathematics (Wikipedia)
Cross-Tradition Connections
Sources
Reader Challenges (0 open reader challenges)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.
View At A Past Year
The atlas records no dated fact of its own for this entry, so there is no other year to choose.