Mathematics Atlas

How Proof Is Made
Sign In
Text size
100%
Theme
Open Question

Is every efficiently checkable problem also efficiently solvable, or is checking genuinely easier than solving?

Open Question

Fifty years of concerted effort by theoretical computer scientists has produced neither a proof that P equals NP nor a proof that it does not; most researchers believe P does not equal NP but this remains an unproven belief, not a result.

What would resolve this A proof either that some NP problem provably cannot be solved in polynomial time (P does not equal NP), or a genuine polynomial-time algorithm for an NP-complete problem (P equals NP); a Clay Mathematics Institute Millennium Prize of one million dollars is offered for a correct resolution either way.
OpenComputational complexity theoryClay Mathematics Institute
Connections

Question On

Source Clay Mathematics Institute
Sources
Clay Mathematics Institute
Clay Mathematics InstituteView the Source
Comments (0)
No comments yet. Be the first to share a thought.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.