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:
- asymptotic complexity (NP is defined in terms of asymptotic complexity.)
- nondeterministic Turing machines (NP is defined in terms of nondeterministic Turing machines.)
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.
Location:
Lecture "P and NP"
Other notes:
- Click on "Preview" to see the lecture videos.
-Paid-
→ Introduction to the Theory of Computation
An undergraduate textbook on automata and the theory of computation.
- Section 7.2, "The class P," pages 256-263
- Section 7.3, "The class NP," pages 264-270
Other notes:
- The material about context-free languages is optional, and has additional prerequisites.
→ Automata Theory, Languages, and Computation
An undergraduate textbook on automata and the theory of computation.
Location:
Section 10.1, "The classes P and NP," pages 426-435
See also
-No Additional Notes-