Skip to content
Tutorials Center
My learning

Topics

Lesson 197 of 225 ยท Advanced Topics

P, NP and Hard Problems

Understand P, NP and NP-complete problems with Python: verify vs solve, SAT, subset sum, TSP, clique, reductions and a 2-approximation for vertex cover.

Some problems have fast algorithms: sorting, shortest paths, minimum spanning trees. Others, however hard people have tried, have only algorithms that blow up as the input grows: the best known solutions for the travelling salesperson problem or for scheduling with many constraints take exponential time in the worst case. Computer scientists have built a theory to describe this divide. It tells you when to stop searching for a perfect fast algorithm and settle for a good-enough one.

In this lesson you will meet the classes P and NP, learn the key idea that separates finding an answer from checking one, see the famous NP-complete problems (SAT, subset sum, TSP, clique, vertex cover), understand reductions, and finish with practical weapons: an approximation algorithm for vertex cover and a heuristic for TSP. This lesson is about ideas and intuition, not formal proofs.

Solving versus checking

A decision problem has a yes/no answer. "Is there a route through all cities of length at most 100?" is a decision problem; "find the shortest route" is its optimization cousin.

  • P is the class of decision problems that can be solved in polynomial time: O(n), O(n log n), O(n^2), O(n^10)... Anything bounded by n raised to a fixed power. Sorting, shortest path and "is this graph connected?" are in P.
  • NP is the class of decision problems where a "yes" answer can be checked in polynomial time, given a hint called a certificate (or witness).

The name NP stands for nondeterministic polynomial time, not "not polynomial". Every problem in P is also in NP: if you can solve it quickly, you can certainly check an answer quickly by solving it again.

A jigsaw puzzle is a good picture. Putting it together may take hours, but if a friend shows you the finished picture, you can verify in seconds that it is correct.

Python Verifying is cheap, searching is expensive

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Checking a certificate is a single pass; finding one by brute force may touch all 2^n subsets. Whether that gap is real or an illusion is the biggest open question in computer science.

P versus NP

Everything in P is in NP. The question P = NP? asks the reverse: is every problem whose solution can be checked quickly also solvable quickly? Almost everyone believes the answer is no, since decades of effort have not produced fast algorithms for the hardest NP problems, but nobody has proved it. The Clay Mathematics Institute offers a million dollars for a proof either way.

TEXT
              believed picture
   +---------------------------------+
   |  NP                             |
   |     +-----------+               |
   |     |     P     |   NP-complete |
   |     | sorting   |   SAT, TSP,   |
   |     | shortest  |   clique,     |
   |     | paths     |   subset sum  |
   |     +-----------+               |
   +---------------------------------+

NP-complete: the hardest problems in NP

A problem is NP-complete if (1) it is in NP and (2) every problem in NP can be turned into it by a fast conversion. So an NP-complete problem is among the hardest in NP: if you find a polynomial-time algorithm for even one of them, all of NP collapses into P.

The first problem proven NP-complete (by Stephen Cook in 1971, and independently by Leonid Levin) was Boolean satisfiability (SAT): given a formula with variables that can be true or false, is there an assignment making it true? Since then thousands of problems have joined the club.

Problem Question Brute force
SAT Can the variables of a formula be set to make it true? 2^n assignments
Subset sum Does some subset sum to a target? 2^n subsets
TSP (decision) Is there a tour through all cities of length at most L? (n-1)! tours
Clique Does the graph contain k vertices that are all connected to each other? C(n, k) subsets
Vertex cover Can k vertices touch every edge? C(n, k) subsets
Graph coloring (3 colors) Can the vertices be colored with 3 colors with no neighbors equal? 3^n colorings

NP-hard means "at least as hard as the hardest problems in NP", without needing to be in NP itself. The optimization version of TSP ("find the shortest tour") is NP-hard. Its decision version ("is there a tour of length at most L?") is NP-complete.

Python SAT by brute force: the cost doubles per variable

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Real SAT solvers are surprisingly good in practice; they solve formulas with millions of variables by using clever pruning. But there is no guarantee for the worst case, which is the whole point of NP-completeness.

Reductions: turning one problem into another

A reduction converts any instance of problem A into an instance of problem B in polynomial time, such that the answer stays the same. If you can solve B fast, you get A for free. Reductions are how NP-completeness is proved: to show that a new problem X is NP-complete, reduce a known NP-complete problem to X, showing that X is at least as hard.

A friendly example: independent set (pick k vertices with no edges between them) reduces to clique (pick k vertices with all edges between them). Flip the graph: complement it by adding every missing edge and removing every existing one. A set that is independent in the original is a clique in the complement, and vice versa.

Python Reduction: independent set becomes clique in the complement graph

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The conversion (complementing the graph) takes polynomial time, so independent set is no harder than clique. Because the same trick works in the other direction, the two are equally hard.

Pseudo-polynomial time: why subset sum is a special case

Subset sum has a dynamic programming solution that runs in O(n * target) time (knapsack uses the same idea). That looks polynomial, but it is not: the input size is the number of bits needed to write the target, so the running time is exponential in the bit length (a target of 60 bits means about 10^18 states). Such algorithms are called pseudo-polynomial. They are great when the numbers are small, which is often the case in practice.

Python Subset sum by DP: fast when numbers are small

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Coping with hard problems

When you meet an NP-hard problem in real life, you rarely give up. You have options:

  1. Small inputs: exponential algorithms are fine for n up to about 20-25 (bitmask DP, meet in the middle).
  2. Special structure: the problem might be easy on trees, planar graphs or small numbers.
  3. Approximation algorithms: polynomial time, with a provable bound on how far from optimal the answer can be.
  4. Heuristics: fast methods with no guarantee, such as greedy choices, local search or simulated annealing.
  5. Exact solvers: SAT and integer-programming solvers that are very good on practical instances.

An approximation: vertex cover within a factor of 2

A vertex cover is a set of vertices that touches every edge. Finding the smallest one is NP-hard. Here is a simple algorithm: repeatedly pick any uncovered edge, add both its endpoints to the cover, and delete all edges those endpoints touch.

Why is the answer at most twice the optimum? The edges we picked share no endpoints (we remove covered edges), so they form a matching. Any cover, including the optimal one, must contain at least one endpoint of each of these picked edges, so the optimum is at least the number of picked edges, m. Our cover has exactly 2m vertices, so it is at most 2 times the optimum.

Python 2-approximation for vertex cover versus the exact answer

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A heuristic: nearest neighbor for TSP

For TSP, a common quick method is: start at city 0 and always go to the nearest unvisited city. It is O(n^2), always produces a valid tour, but offers no guarantee: it can be far from optimal. Compare it with brute force on a small instance.

Python Nearest neighbor heuristic versus the optimal tour

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

On this instance the greedy tour is about 21% longer than the optimal one (31.1 against 25.57), which shows why a heuristic comes without a guarantee.

Common mistakes

  • "NP means not polynomial." It means "checkable in polynomial time". Every problem in P is also in NP.
  • "NP-complete means impossible." It means no known fast worst-case algorithm. Small instances and many special cases are solved every day.
  • Reducing in the wrong direction. To prove X hard, reduce a known hard problem to X, not X to the hard problem.
  • Confusing decision and optimization versions. The decision version is the one in NP; the optimization version is NP-hard.
  • Treating pseudo-polynomial as polynomial. O(n * target) grows with the value of the number, not its bit length.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does the class NP contain?

    NP stands for nondeterministic polynomial time. P is contained in NP, and the open question is whether they are equal.
  2. 2. If someone finds a polynomial-time algorithm for SAT, what follows?

    SAT is NP-complete: every problem in NP reduces to it in polynomial time, so a fast SAT algorithm would solve all of NP quickly.
  3. 3. Which statement about the vertex cover 2-approximation is correct?

    The picked edges form a matching, so the optimum needs at least one vertex per picked edge, while the algorithm adds two.
  4. 4. Why is the O(n * target) subset sum DP called pseudo-polynomial?

    The input length is measured in bits, and a target with b bits can be about 2^b. That makes O(n * target) exponential in the input size.
  5. 5. How do you show that a new problem X is NP-hard?

    If a known hard problem can be turned into X quickly, then a fast algorithm for X would make the known problem easy too, so X must be at least as hard.

Summary

  • P: solvable in polynomial time. NP: yes-answers checkable in polynomial time with a certificate. P is inside NP; whether P = NP is open, and most experts believe not.
  • NP-complete problems (SAT, subset sum, decision TSP, clique, vertex cover, 3-coloring) are the hardest in NP: a fast algorithm for one gives a fast algorithm for all.
  • Reductions convert one problem into another and are how hardness is proved; independent set to clique is done by complementing the graph.
  • Subset sum has a pseudo-polynomial DP that is fast for small numbers.
  • In practice, use small-input exponential search, special structure, approximation algorithms (vertex cover within factor 2), heuristics (nearest neighbor), or good solvers.

Next: Online and Streaming Algorithms