Skip to main content

Class P, class NP and NP-complete

Short answer

P: decision problems solvable in polynomial time by a deterministic TM (e.g., shortest path). NP: problems with polynomial-time verifiable certificates (e.g., SAT). NP-complete problems are the hardest in NP; every NP problem reduces to them. P ⊆ NP; if P ≠ NP, NP-complete problems are not in P. If any NP-complete problem is in P, then P=NP.

Define class P and class NP problems with example. How do they relate to NP-complete problems?

Class P

P is the class of decision problems solvable by a deterministic Turing machine in polynomial time, i.e. in O(nᵏ) steps for some constant k.

Examples: sorting, shortest path (Dijkstra), minimum spanning tree, searching, primality testing, 2-SAT, and checking whether a graph is connected.

Class NP

NP is the class of decision problems solvable by a non-deterministic Turing machine in polynomial time. Equivalently, if the answer is "yes", there is a short certificate (proof) that can be verified in polynomial time by a deterministic machine.

Examples:

  • SAT: is there a truth assignment satisfying the formula? (Certificate: the assignment.)
  • Hamiltonian cycle: does a graph have a cycle through every vertex once? (Certificate: the cycle.)
  • Subset sum, CLIQUE, Vertex cover, TSP (decision version).

Relation of P, NP and NP-complete

  • P ⊆ NP, since a deterministic TM is a special case of a non-deterministic TM. Whether P = NP is the major open problem.
  • A problem is NP-complete if it is in NP and every problem in NP reduces to it in polynomial time. NP-complete problems are the hardest problems in NP.
  • If P ≠ NP, then NP-complete problems are not in P. If any one NP-complete problem is in P, then P = NP.
   Assuming P ≠ NP:
   ┌─────────────────────────┐
   │ NP                      │
   │   ┌──────┐  ┌────────┐  │
   │   │  P   │  │  NP-   │  │
   │   │      │  │complete│  │
   │   └──────┘  └────────┘  │
   └─────────────────────────┘

Examples: SAT and Hamiltonian cycle are NP-complete; sorting is in P; the Cook–Levin theorem proved the first NP-complete problem (SAT).

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Theory of Computation chapter 6 questions →