P, NP and NP-completeness

Advanced

Introduction

Decidability asks whether a problem can be solved at all. Complexity asks how much time it needs. Some problems, such as sorting or shortest paths, have fast algorithms. Others, such as scheduling exams with no clashes, packing boxes or finding a subset of numbers with a given sum, seem to need a search through exponentially many possibilities. Yet for all of these, checking a proposed answer is easy. That gap between solving and checking is the heart of the P vs NP question.

How it works

We measure time as a function of the input size n. An algorithm runs in polynomial time if its steps are at most about nᵏ for a fixed k. Polynomial time is the working definition of "efficient": n³ for n = 1,000 is a billion steps, but 2ⁿ for n = 100 is more than the number of atoms in the universe.

  • P is the class of yes-or-no problems that can be decided in polynomial time.
  • NP is the class of problems where every yes-answer has a short certificate that can be verified in polynomial time.

For subset sum ("is there a subset of these numbers that adds up to the target?") the certificate is the subset itself, and checking it is one addition per number. Finding it by brute force may need all 2ⁿ subsets.

Every problem in P is in NP: the verifier can ignore the certificate and solve the problem. Whether P = NP, whether every easily checked problem is also easily solved, is unknown. It is one of the Millennium Prize Problems.

Reductions and NP-completeness. Problem A reduces to B in polynomial time if a fast translation turns every A-instance into a B-instance with the same answer. A problem is NP-complete if it is in NP and every NP problem reduces to it. The Cook–Levin theorem shows that SAT is NP-complete: given a formula of AND, OR and NOT over boolean variables, is there an assignment that makes it true? Thousands of problems have since been shown NP-complete, including subset sum, graph colouring, the travelling-salesman decision problem and Sudoku of any size. A fast algorithm for any one of them would give fast algorithms for all of NP.

Syntax

def verify(certificate):          # polynomial: check the evidence
    ...
for candidate in all_candidates:  # brute force: often 2ⁿ candidates
    if verify(candidate):
        return candidate

Example

from itertools import combinations

numbers = [3, 34, 4, 12, 5, 2]
target = 9


def verify(subset):
    return all(x in numbers for x in subset) and sum(subset) == target


def search():
    tried = 0
    for size in range(len(numbers) + 1):
        for subset in combinations(numbers, size):
            tried += 1
            if sum(subset) == target:
                return subset, tried
    return None, tried


answer, tried = search()
print("certificate found:", answer, "after trying", tried, "subsets")
print("checking it takes one pass:", verify(answer))
for n in [10, 20, 30, 40]:
    print(f"n={n}: up to {2 ** n:,} subsets to search")
Open in compiler

Line by line

  1. verify checks a proposed subset: every element must come from the list, and the sum must be the target. That is one quick pass.
  2. search tries subsets of size 0, 1, 2 and so on, counting how many it tried, until one adds up to 9.
  3. The certificate (4, 5) is found after 18 tries, and verifying it is immediate.
  4. The last lines show how the number of subsets doubles with each extra number: 40 numbers already give over a trillion subsets.

Expected result

certificate found: (4, 5) after trying 18 subsets
checking it takes one pass: True
n=10: up to 1,024 subsets to search
n=20: up to 1,048,576 subsets to search
n=30: up to 1,073,741,824 subsets to search
n=40: up to 1,099,511,627,776 subsets to search

In the real world

NP-complete problems are everywhere: timetabling, route planning, chip layout, protein folding and resource allocation. Knowing a problem is NP-complete tells engineers to stop looking for a perfect fast algorithm and use heuristics, approximations or SAT solvers, which handle many real instances well. Modern cryptography depends on the belief that some problems (such as factoring) are hard to solve but easy to check.

Common mistakes

  • Thinking NP means "not polynomial": it means nondeterministic polynomial, problems with fast verifiers.
  • Calling a problem hard because one algorithm is slow: hardness is about the best possible algorithm.
  • Reducing in the wrong direction: to show B is NP-hard, reduce a known NP-complete problem to B.
  • Believing NP-complete means unsolvable: these problems are decidable, just apparently slow in the worst case.

Best practices

  • Separate "check a proposed answer" from "find an answer" when analysing a problem.
  • Measure how brute force grows by counting candidates, as the example does.
  • When a problem is NP-complete, look for structure in your actual inputs, a good heuristic, or a SAT or ILP solver.

Summary

P contains problems decidable in polynomial time; NP contains problems whose yes-answers can be verified in polynomial time from a certificate. P is inside NP, and whether they are equal is unknown. NP-complete problems such as SAT and subset sum are the hardest problems in NP: a polynomial algorithm for one would solve them all.

Quick check

1. What defines the class NP?
2. For subset sum, what is a natural certificate?
3. If one NP-complete problem had a polynomial-time algorithm, then…
4. Which theorem shows that SAT is NP-complete?

Key takeaways

  • P is "easy to solve"; NP is "easy to check a proposed answer".
  • Every problem in P is in NP; whether P = NP is the biggest open question in computer science.
  • An NP-complete problem, such as SAT, is as hard as every problem in NP.

Practice problems for this lesson

My notes

Write down what you want to remember from this lesson. Notes are saved on this device as you type, and appear on your dashboard.