This note is part of my learning notes on Data Structures & Algorithms.

Classes of Problems

Polynomial Time (P)

The class P consists of those problems that are solvable in polynomial time.
More specifically, they are problems that can be solved in time O(nk)O(n^k) for some constant kk, where nn is the size of the input to the problem.

Nondeterministic Polynomial Time (NP)

NP is the class of decision problems for which a given solution can be verified as correct or incorrect in polynomial time by a deterministic Turing machine.

A decision problem LL is in NP if there exists a polynomial-time verifier VV such that for every instance x∈Lx \in L, there exists a certificate yy (with size polynomial in the size of xx) for which V(x,y)=trueV(x,y) = true.

Any problem in P is also in NP, since if a problem is in P then we can solve it in polynomial time without even being supplied a certificate.

NP-Complete

NP-Complete (NPC) problems are the hardest problems in NP in the sense that every problem in NP can be reduced to them in polynomial time. If an NP-Complete problem can be solved in polynomial time, then every problem in NP can also be solved in polynomial time.

A decision problem LL is NP-Complete if

  • L∈NPL \in NP
  • For every problem L′∈NPL' \in NP, there exists a polynomial time reduction from L′L' to LL

NP-Hard

NP-Hard problems are at least as hard as the hardest problems in NP. An NP-Hard problem does not have to be in NP (i.e., it does not have to be a decision problem).

A decision problem LL is NP-Hard if

  • For every problem L′∈NPL' \in NP, there exists a polynomial time reduction from L′L' to LL

Strongly NP-hard

A problem is strongly NP-hard if it remains NP-hard even when all the numerical parameters are bounded by a polynomial in the length of the input. Essentially, even small, compact instances of the problem are difficult to solve.

Weakly NP-hard

A problem is weakly NP-hard if it is NP-hard in general but may be solvable in polynomial time when its numerical parameters are bounded by a polynomial in the length of the input.

Relationships

  • NP ⊆\subseteq NP-Hard: Every problem in NP is reducible to every problem in NP-Hard.
  • NP-Complete ⊆\subseteq NP-Hard: Every NP-Complete problem is also NP-Hard.
  • NP-Complete ⊆\subseteq NP: Every NP-Complete problem is also in NP.
  • P ⊆\subseteq NP: Every problem that can be solved in polynomial time (P) can also be verified in polynomial time (NP).
  • P ≠ NP (conjectured): It’s an open question in computer science whether every problem whose solution can be verified in polynomial time can also be solved in polynomial time.

Examples

  • P: Merge Sort, Quick Sort, Dijkstra’s problem
  • NP: Hamiltonian Path, Subset Sum, Sudoku
  • NP-Complete: Traveling Salesman Problem
  • Strongly NP-Hard: 3SAT (Boolean satisfiability) problem
  • Weakly NP-Hard: Knapsack problem