represents the class of problems with polynomial time solutions. the precise definition uses the time complexity of Turing machines. these are efficiently solvable, or tractable, problems.
Example
finding the most connected person falls in , for example.
NP-complete
represents a class of problems with no known efficient solutions. the precise definition uses non-deterministic Turing machines.
Example
for example, finding the largest clique is such a problem.
what separates from other categories is that if we can find an efficient solution to one problem in the class, then there must exist a polynomial time algorithm for every problem.
- no known proof that such problems cannot be solved efficiently. there is a million dollars waiting for anyone who can solve this.
Example
Cook’s theorem states that the Boolean satisfiability problem is . if we can find a polynomial time solution for SAT, then there must exist a polynomial time solution for all other problems.
Example: Traveling Salesperson Problem
given a map of cities with distances between them, find a tour that visits each city exactly once with minimum possible distance travelled.
it turns out this problem is also .