# 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-