Complexity classes
The classes P, NP, NP-complete and NP-hard, checking a certificate, polynomial reduction, the reference problems (SAT, knapsack, travelling salesman, colouring) and the size each cost lets you handle in a given time.
- 25 cards
- 7 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- On the timeline
- The numbers
- Scenarios
- Understand
A few cards from the deck
Class P: what is it?
Show the answer
The set of decision problems that an algorithm solves in time polynomial in the size of the input.
Sorting, finding a shortest path or testing primality all belong here. "Polynomial" means bounded by n^k for a fixed k, which 2ⁿ never satisfies.
What does it mean for a problem to be in NP?
- A proposed solution can be checked in polynomial time
- No polynomial algorithm can solve it
- The best known algorithm to solve it is exponential
- It can be solved in polynomial time only on a quantum machine
Show the answer
A proposed solution can be checked in polynomial time
NP stands for "non-deterministic polynomial", not "non-polynomial". Every problem in P is also in NP: solving fast makes checking fast.
A proposed solution is called a …; a problem is in NP if the certificate can be checked in … time.
Show the answer
A proposed solution is called a certificate; a problem is in NP if the certificate can be checked in polynomial time.
For SAT, the certificate is an assignment of the variables: evaluating it clause by clause takes time linear in the size of the formula.
Class NP: what is it?
Show the answer
The set of decision problems whose proposed solution, called a certificate, can be checked in polynomial time.
The criterion is about checking, not searching: nobody knows whether finding the solution can always be as fast. That is the P = NP question.