NP complexity class

(1.7 hours to learn)

Summary

NP, or "nondeterministic polynomial," is the complexity class of problems with "polynomial time verifiers." I.e., if the problem has a solution, it must be possible to verify the solution in polynomial time, even if finding the solution is much harder. Equivalently, it is the class of problems which can be solved efficiently by nondeterministic Turing machines. The "P vs. NP" question, whether all NP problems can be solved in worst-case polynomial time, is the central question in computational complexity theory.

Context

This concept has the prerequisites:

Goals

  • Define the complexity classes P and NP
  • Be able to show that problems are in NP
  • Be aware of the "P vs. NP" problem and why it's important

Core resources (read/watch one of the following)

-Free-

Coursera: Automata
An introductory course on automata and the theory of computation.
Author: Jeffrey D. Ullman
Other notes:
  • Click on "Preview" to see the lecture videos.

-Paid-

See also

-No Additional Notes-