notesonly.in

One notebook for every subject — open it anywhere.

Log in

Complexity Classes: P, NP and NP-Complete For students.

EngineeringTry the interactive 3D model →

P is the class of problems solvable in polynomial time — time growing like n squared, n cubed, or n to the k for fixed k, where n is the input size. Sorting a list or finding the shortest path in a map are in P: doubling the input multiplies the work by only a manageable factor.

NP is the class of problems whose proposed solutions can be verified in polynomial time. Handed a completed Sudoku grid, you can check it quickly even though finding it is hard. The biggest open question in computer science is whether P equals NP — whether every efficiently checkable problem is also efficiently solvable.

Key Concepts

  • Polynomial time: running time O(n^k) for constant k — the formal definition of "efficient".
  • Exponential time: running time like O(2^n); each added input element doubles the work — quickly infeasible.
  • Verification: an NP problem ships with a certificate (proposed solution) checkable in polynomial time.
  • Polynomial-time reduction: transforming problem A into B efficiently, so solving B solves A.
  • NP-complete: problems in NP to which every NP problem reduces — the hardest in NP. NP-hard problems are at least as hard but need not be in NP.

Formulas

  • Polynomial bound: T(n) = O(n^k), e.g. T(n) = 3n^2 + 5n + 2. For n = 1,000, n^2 = 1,000,000 operations — trivial for a modern CPU.
  • Exponential bound: T(n) = O(2^n). For n = 60, 2^60 ≈ 1.15 x 10^18 operations — at 10^9 ops/sec, about 1.15 x 10^9 seconds, roughly 36 years.
  • Crossover: for n = 100, n^3 = 1,000,000 (under a millisecond) while 2^100 ≈ 1.27 x 10^30 — vastly more than the seconds since the Big Bang (≈ 4.3 x 10^17).

Worked Example

The traveling salesperson problem: visit 6 cities, return home, minimize distance. Verification is easy. Proposed tour A-C-B-F-D-E-A with edge weights 4, 7, 3, 9, 5, 6:

  1. Add: 4 + 7 = 11; 11 + 3 = 14; 14 + 9 = 23; 23 + 5 = 28; 28 + 6 = 34. Total 34 km.
  2. Check each city appears once (6 checks) and the tour returns to start (1 check) — about 13 operations, polynomial in n = 6. Verified: the problem is in NP.

Finding the best tour is the hard part: (6-1)!/2 = 60 tours to compare. For 25 cities: 24!/2 ≈ 3.1 x 10^23 tours — impossible to enumerate. That is the P vs NP gap: checking is cheap, searching is brutal.

Common Misconceptions

  • NP means "non-polynomial". It means nondeterministic polynomial time — problems verifiable in polynomial time.
  • NP-complete problems cannot be solved. They can — just with no known polynomial-time algorithm. Small inputs solve fine; approximations handle large ones.
  • P vs NP is settled. It is the most famous open problem in the field; most experts believe P ≠ NP, but it is unproved.

Real-World Applications

  • Logistics: delivery routing, airline scheduling, warehouse packing are NP-hard — solved daily with heuristics.
  • Cryptography: RSA relies on believed-hard problems; if P = NP, much encryption collapses.
  • Circuit design: transistor placement minimizing wire length is NP-hard; tools use approximations.
  • Bioinformatics: protein folding and genome assembly need NP-hard optimization at scale.

P is what computers solve efficiently, NP is what they check efficiently, and NP-complete problems sit at the frontier. Whether that frontier is real or an illusion of current knowledge — the P vs NP question — remains computer science's deepest unsolved problem.

Related blogs