P vs NP

Definitions

1. The most important open question in computer science: whether every problem whose solution can be verified quickly (NP) can also be solved quickly (P). A Clay Millennium Prize Problem worth $1 million.

   In plain English: Can every problem that's easy to check also be easy to solve? Nobody knows, and it's the biggest unsolved puzzle in computing.

   Example: "If you could prove P = NP, you'd break most of modern cryptography — and win a million dollars doing it."

Related Terms

• Computability
• Complexity Class
• Reduction
• SAT Problem
• Kolmogorov Complexity