theory completness satisfiability

Completness and satisfiability

The P vs NP problem is one of the most famous open problems in theoretical computer science. At its core, it asks whether or not all problems whose solutions can be verified in polynomial time, can also be solved in polynomial time. The class of problems that can be solved in polynomial time is called P, while the class of problems whose solutions can be verified in polynomial time is called NP.