Skip to content
LumenaryAcademy
Algorithms 60 min

Hard problems: P, NP and coping

Why some problems resist every clever idea, how reductions prove it, and what engineers do when the problem in front of them is NP-hard.

Code tested · 7AI-draftedAwaiting review by a computer scientist

Your guides: Chloe · The Computer Scientist, Margaret · The Experimenter, Gideon · The Verifier

MotivationH

When cleverness runs out

A university registrar has 400 exams and 12 time slots. Two exams that share a student cannot be in the same slot. Is there a timetable? A delivery company has 60 stops for one van. What is the shortest route that visits them all and comes home? A chip designer has a circuit with a million gates and wants to know whether any input can make two supposedly equivalent outputs differ.

Each of these looks like the problems you solved earlier in this level, and you might expect another clever greedy rule or dynamic programme to crack it. For these three, nobody has ever found one, despite more than fifty years of effort by many of the best minds in the field. Better still, we can prove that they stand or fall together: a fast algorithm for any one of them would give fast algorithms for all of them and for thousands of other problems. That web of equivalences is the theory of NP-completeness, and knowing it is a practical skill. When you recognise that your problem is NP-hard, you stop searching for a perfect fast algorithm that probably does not exist and reach for the tools that work: special structure, approximation, heuristics, and solvers.

This lesson gives the engineer's version of the theory. Lumenary Math's Computational complexity lesson gives the mathematician's, with Turing machines and full proofs, and Computability covers the problems no algorithm can solve at all, however much time it is given.

DefinitionsH

Decision problems, P and NP

Complexity theory classifies problems, not programs, and it is cleanest for yes-or-no questions.

Definition— decision problem

A decision problem is a question with a yes-or-no answer about an input written as a string of symbols. Its size nn is the length of that string. Examples: "Is this number prime?" "Can this graph be coloured with 3 colours so that adjacent vertices differ?" "Is there a tour through these cities of total length at most BB?"

Optimisation problems ("what is the shortest tour?") have decision versions ("is there a tour of length at most BB?"), and the two are usually equally hard: with a decision procedure you can binary-search for the optimal BB.

Definition— P

P is the class of decision problems that some algorithm solves in time O(nc)O(n^c) for a constant cc: polynomial time.

Sorting, shortest paths, minimum spanning trees, matching, primality testing and linear programming are all in P. Polynomial time is the theory's stand-in for "efficient". It is a coarse stand-in, since n50n^{50} is not efficient, but it is robust: it does not depend on the programming language or machine model, and the polynomial-time algorithms people actually find almost always have small exponents.

Definition— NP

NP is the class of decision problems for which every yes-instance has a certificate (a proposed solution) of polynomial length that a polynomial-time verifier can check. If the answer is no, no certificate fools the verifier.

For 3-colouring, the certificate is a colouring: check each edge's endpoints differ, linear time. For the travelling salesperson's decision version, it is a tour: check that it visits every city once and add up its length. For SAT, the satisfiability problem for Boolean formulas, it is an assignment of true or false to each variable: evaluate the formula. NP is the class of problems whose solutions are easy to check, whether or not they are easy to find. (The name means "nondeterministic polynomial time", from an equivalent definition with a machine that may guess; it does not mean "not polynomial".) Every problem in P is in NP, since the verifier can ignore the certificate and solve the problem itself, so P⊆NP\mathrm{P} \subseteq \mathrm{NP}. Whether the inclusion is strict is the P versus NP question.

python
from itertools import product

# A formula in conjunctive normal form (CNF): a list of clauses, each a list of literals.
# Literal 3 means "x3 is true" and -3 means "x3 is false" (the DIMACS convention SAT solvers use).
# The formula is true when every clause contains at least one true literal.
formula = [[-1, -3, -4], [-2, 3, 4], [-1, -3, 5], [2, -4, 5], [1, -2, -3], [1, 2, 4],
           [1, 3, -4], [-2, 4, -5], [-1, 2, 3], [2, -3, -5], [3, -4, -5]]

def satisfies(clauses, assignment):
    """The verifier: does the assignment {variable: bool} make every clause true? Linear time."""
    return all(any(assignment[abs(lit)] == (lit > 0) for lit in clause) for clause in clauses)

certificate = {1: True, 2: True, 3: False, 4: True, 5: False}
print("the certificate checks out:", satisfies(formula, certificate))

# Without a certificate: try all 2^n assignments.
n, tried = 5, 0
for values in product([False, True], repeat=n):
    tried += 1
    assignment = dict(zip(range(1, n + 1), values))
    if satisfies(formula, assignment):
        print(f"search found {assignment} after {tried} of {2 ** n} assignments")
        break

for n in (20, 50, 100, 300):
    print(f"n = {n:>3}: checking one assignment ~ {n} steps; trying all of them ~ 2^{n} = {2 ** n:.1e}")
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

Checking grows linearly; blind search grows as 2n2^n. At n=300n = 300 the search space is larger than the number of atoms in the observable universe (roughly 108010^{80}). The question is whether something fundamentally better than blind search always exists.

ExplanationH

Reductions and NP-completeness

How can we say a problem is hard when we cannot prove that it needs exponential time? By comparison. A reduction shows that one problem is no harder than another.

Definition— polynomial-time reduction

Problem AA reduces to problem BB, written A≤pBA \le_p B, if there is a polynomial-time function ff that turns any instance xx of AA into an instance f(x)f(x) of BB with the same answer: xx is a yes-instance of AA exactly when f(x)f(x) is a yes-instance of BB.

If A≤pBA \le_p B and BB has a polynomial-time algorithm, so does AA: transform, then solve. Read the other way: if AA is hard, BB must be at least as hard. The direction matters. To show your new problem BB is hard, you reduce a known hard problem to BB, not BB to it. Reducing your problem to SAT shows only that SAT is powerful enough to express it, which is useful in practice (it means you can use a SAT solver) but says nothing about hardness.

Definition— NP-hard, NP-complete

A problem is NP-hard if every problem in NP reduces to it. It is NP-complete if it is NP-hard and in NP.

Theorem— Cook–Levin (1971)

SAT is NP-complete.

The idea of the proof is that a verifier's computation, step by step, is itself a Boolean circuit of polynomial size; a formula can say "this computation is a valid run that accepts", and the formula is satisfiable exactly when some certificate makes the verifier accept. Stephen Cook published it in 1971 and Leonid Levin found it independently in the Soviet Union. A year later Richard Karp showed, by chains of reductions, that 21 problems from across combinatorics and operations research were NP-complete too, including graph colouring, clique, vertex cover, Hamiltonian cycle and knapsack. Since then thousands more have joined the list. Once one problem is known NP-complete, each new one needs only a single reduction from any of them.

A note on what "complete" buys: if any NP-complete problem has a polynomial-time algorithm, then every problem in NP does, and P = NP. If any one of them provably needs super-polynomial time, they all do.

Hard problems and their easy cousins

Hardness is fragile, and that is good news for engineers. Small changes to a problem can move it into P:

Hard (NP-complete)Easy relative (in P)
3-colouring a graph2-colouring: a graph is 2-colourable exactly when it is bipartite; breadth-first search decides it in linear time
3-SAT: clauses of three literals2-SAT: clauses of two literals, solved in linear time via strongly connected components
Travelling salesperson: visit every vertex onceShortest path between two vertices; Euler tour: use every edge once
Longest simple pathShortest path (with non-negative weights)
Vertex cover in a general graphVertex cover in a bipartite graph (via maximum matching) or a tree (dynamic programming)

A reduction you can run: colouring as satisfiability

Reductions also run towards SAT in everyday engineering, because SAT solvers are so good. Here is the reduction from kk-colouring to SAT. For each region rr and colour cc, introduce a variable xr,cx_{r,c} meaning "region rr gets colour cc". Then write three kinds of clause: every region gets at least one colour (xr,1∨⋯∨xr,kx_{r,1} \lor \cdots \lor x_{r,k}); no region gets two (¬xr,c∨¬xr,c′\lnot x_{r,c} \lor \lnot x_{r,c'} for each pair of colours); neighbours differ (¬xu,c∨¬xv,c\lnot x_{u,c} \lor \lnot x_{v,c} for each border and each colour). For nn regions, mm borders and kk colours that is n+n(k2)+mkn + n\binom{k}{2} + mk clauses, polynomial in the input. The code below builds the formula for the map of South America and hands it to a minimal SAT solver.

python
from itertools import combinations

borders = {
    "Argentina": ["Bolivia", "Brazil", "Chile", "Paraguay", "Uruguay"],
    "Bolivia": ["Brazil", "Chile", "Paraguay", "Peru"],
    "Brazil": ["Colombia", "French Guiana", "Guyana", "Paraguay", "Peru", "Suriname", "Uruguay", "Venezuela"],
    "Chile": ["Peru"],
    "Colombia": ["Ecuador", "Peru", "Venezuela"],
    "Ecuador": ["Peru"],
    "Guyana": ["Suriname", "Venezuela"],
    "Suriname": ["French Guiana"],
}
regions = sorted(set(borders) | {b for bs in borders.values() for b in bs})
edges = [(u, v) for u in borders for v in borders[u]]

def colouring_to_cnf(regions, edges, k):
    """The reduction: a CNF formula that is satisfiable exactly when the map is k-colourable."""
    var = {(r, c): i * k + c + 1 for i, r in enumerate(regions) for c in range(k)}  # x[r, c]
    clauses = []
    for r in regions:
        clauses.append([var[r, c] for c in range(k)])                      # at least one colour
        for c1, c2 in combinations(range(k), 2):
            clauses.append([-var[r, c1], -var[r, c2]])                     # at most one colour
    for u, v in edges:
        for c in range(k):
            clauses.append([-var[u, c], -var[v, c]])                       # neighbours differ
    return clauses, var

def dpll(clauses, assignment=None, stats=None):
    """A minimal DPLL SAT solver: unit propagation, then branch. Returns a model or None."""
    assignment = dict(assignment or {})
    stats = stats if stats is not None else {"branches": 0}
    while True:                                   # unit propagation
        simplified, unit = [], None
        for clause in clauses:
            if any(assignment.get(abs(l)) == (l > 0) for l in clause):
                continue                          # clause already satisfied
            rest = [l for l in clause if abs(l) not in assignment]
            if not rest:
                return None                       # every literal false: conflict
            if len(rest) == 1:
                unit = rest[0]
            simplified.append(rest)
        clauses = simplified
        if unit is None:
            break
        assignment[abs(unit)] = unit > 0          # a one-literal clause forces its literal
    if not clauses:
        return assignment
    stats["branches"] += 1
    lit = clauses[0][0]                           # branch on the first open literal
    for value in (lit > 0, lit < 0):
        model = dpll(clauses, {**assignment, abs(lit): value}, stats)
        if model is not None:
            return model
    return None

for k in (3, 4):
    clauses, var = colouring_to_cnf(regions, edges, k)
    stats = {"branches": 0}
    model = dpll(clauses, stats=stats)
    print(f"{k} colours: {len(var)} variables, {len(clauses)} clauses, {stats['branches']} branches ->",
          "unsatisfiable" if model is None else "satisfiable")
    if model:
        colour = {r: c for (r, c), x in var.items() if model.get(x)}
        assert all(colour[u] != colour[v] for u, v in edges)
        names = ["red", "green", "blue", "gold"]
        print("   ", ", ".join(f"{r}: {names[colour[r]]}" for r in regions))
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

Three colours are impossible, and the reason is visible on the map: Argentina, Bolivia, Brazil and Paraguay all border one another, so they need four different colours. The solver found that out in a handful of branches, because unit propagation (when a clause has one undecided literal left, that literal is forced) does most of the reasoning. That is the DPLL algorithm of the early 1960s. Modern solvers add conflict-driven clause learning: every time they hit a contradiction, they work out which earlier decisions caused it and add a new clause that forbids that combination forever.

IntuitionH

What P versus NP would mean

The Clay Mathematics Institute lists P versus NP among its seven Millennium Prize Problems, with a million-dollar prize for a proof either way. Most researchers believe P≠NP\mathrm{P} \ne \mathrm{NP}, for reasons that are evidence rather than proof: decades of failed attempts at fast algorithms for thousands of NP-complete problems from unrelated fields, and the intuition that recognising a good solution should be easier than producing one. Known proof techniques have also been shown unable to settle the question on their own (the "relativisation" and "natural proofs" barriers), which is part of why it is so hard.

If P = NP with a practical algorithm, the world would change. Any problem whose answers can be checked quickly could be solved quickly: optimal schedules, routes and chip layouts; and, since a proof is a certificate a computer can check, finding proofs of theorems of reasonable length would become a mechanical search. Most of today's public-key cryptography would fall, because recovering a secret key from public information is a search problem whose answer is easy to check (see Applied cryptography).

But P = NP might not be practical. A proof could give an algorithm running in n100n^{100} time, or show only that an algorithm exists without constructing it.

If P ≠ NP, as expected, nothing changes in practice: we will have confirmed that no algorithm solves every instance of an NP-complete problem in polynomial time. It would not mean that every instance is hard, that good approximations are impossible, or that cryptography is secure; the security of specific systems rests on specific problems, such as factoring, that are not known to be NP-complete.

Kurt Gödel asked a version of the question in a 1956 letter to John von Neumann, wondering how many steps a machine would need to decide whether a statement has a proof of a given length. The question was formalised only in the early 1970s.

Worked examplesH

Coping: what engineers actually do

NP-hardness is a statement about the worst case over all inputs, assuming P ≠ NP. Your inputs are not all inputs, and you may not need the exact optimum. That leaves a lot of room.

1. Look for structure

Real instances often have properties that put them in an easy special case. Assigning lectures with fixed start and end times to rooms is colouring an interval graph, which a greedy sweep solves optimally. Many graphs from road networks or circuits have small treewidth, which makes dynamic programming feasible. Sometimes a natural parameter is small: deciding whether a graph has a vertex cover of size at most kk takes about 2k⋅m2^k \cdot m steps by branching (some endpoint of each edge must be in the cover, so try each), which is fast for k=20k = 20 even when the graph has millions of edges. This is parameterised complexity: the exponential part depends only on the parameter.

2. Accept an approximation, with a guarantee

An approximation algorithm runs in polynomial time and returns a solution within a proven factor of optimal.

Definition— vertex cover

A vertex cover of a graph is a set CC of vertices that touches every edge: for each edge {u,v}\{u, v\}, u∈Cu \in C or v∈Cv \in C. Finding a smallest one is NP-hard.

The algorithm: go through the edges; whenever an edge has neither endpoint in CC yet, add both endpoints.

Theorem— The matching algorithm is a 2-approximation for vertex cover

The set CC it returns is a vertex cover, and ∣C∣≤2⋅OPT|C| \le 2 \cdot \mathrm{OPT}, where OPT is the size of a smallest vertex cover.

Proof

It is a cover: every edge is examined, and after its turn at least one of its endpoints is in CC; later steps only add vertices. It is small: let MM be the set of edges whose endpoints were added. No two edges of MM share a vertex, because once an edge's endpoints are in CC, any later edge touching them is skipped. Any vertex cover, the optimal one included, must contain an endpoint of each edge in MM, and since these edges are disjoint those endpoints are all different. So OPT≥∣M∣\mathrm{OPT} \ge |M|, and ∣C∣=2∣M∣≤2⋅OPT|C| = 2|M| \le 2 \cdot \mathrm{OPT}.

∎

The proof has the shape of almost every approximation argument: find a lower bound on the optimum (here, the size of any matching) that you can compute, and compare your answer with the bound rather than with the unknown optimum. The same algorithm can be read as rounding a linear program: write vertex cover as an integer linear program (minimise ∑vxv\sum_v x_v subject to xu+xv≥1x_u + x_v \ge 1 for every edge, xv∈{0,1}x_v \in \{0, 1\}), relax to 0≤xv≤10 \le x_v \le 1, solve it in polynomial time, and take every vertex with xv≥12x_v \ge \tfrac12. That also gives a factor of 2, and it is a pattern you will meet in real optimisation work.

How good can approximation get? It depends sharply on the problem. For travelling salesperson with distances that obey the triangle inequality, doubling a minimum spanning tree (from Spanning trees) gives a factor of 2, and Christofides' algorithm of 1976 gives 1.5; in 2021 Karlin, Klein and Oveis Gharan finally improved on 1.5, by a minuscule amount. For TSP with arbitrary distances, no constant factor is achievable at all unless P = NP. For vertex cover, nobody knows how to beat 2 by any constant, and under a widely studied conjecture (the Unique Games Conjecture) nobody can.

3. Use heuristics and local search

A heuristic is a method that usually works well but comes with no guarantee. Nearest-neighbour builds a tour by always going to the closest unvisited city; 2-opt then repeatedly reverses a segment of the tour whenever that shortens it, stopping at a local optimum. Simulated annealing, tabu search and genetic algorithms are more elaborate ways of escaping local optima.

python
import random
from itertools import combinations

def matching_cover(edges):
    """The 2-approximation: take both ends of any edge not yet covered."""
    cover = set()
    for u, v in edges:
        if u not in cover and v not in cover:
            cover |= {u, v}
    return cover

def greedy_degree_cover(n, edges):
    """A natural heuristic with no constant-factor guarantee: repeatedly take the busiest vertex."""
    remaining, cover = set(edges), set()
    while remaining:
        degree = {}
        for u, v in remaining:
            degree[u] = degree.get(u, 0) + 1
            degree[v] = degree.get(v, 0) + 1
        best = max(sorted(degree), key=degree.get)
        cover.add(best)
        remaining = {e for e in remaining if best not in e}
    return cover

def optimum_cover_size(n, edges):
    """The exact answer by brute force, smallest subsets first: exponential, fine for n <= 16."""
    for size in range(n + 1):
        for subset in combinations(range(n), size):
            s = set(subset)
            if all(u in s or v in s for u, v in edges):
                return size

rng = random.Random(42)
worst = 0
print(" n  edges  optimum  matching  greedy")
for trial in range(8):
    n = rng.randint(10, 14)
    edges = [(u, v) for u, v in combinations(range(n), 2) if rng.random() < 0.3]
    rng.shuffle(edges)
    opt = optimum_cover_size(n, edges)
    m, g = len(matching_cover(edges)), len(greedy_degree_cover(n, edges))
    worst = max(worst, m / opt)
    print(f"{n:2} {len(edges):6} {opt:8} {m:9} {g:7}")
print(f"worst matching ratio seen: {worst:.2f} (the theorem promises at most 2)")
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

Look at the columns. The algorithm with the guarantee is noticeably worse on these random graphs than the greedy heuristic without one, which hits the optimum every time here. This is common: a worst-case guarantee protects you against the worst input, while a heuristic is tuned for typical ones. (Greedy-by-degree can be forced to be a logarithmic factor away from optimal on specially built graphs.) In practice engineers often run both, and use the guarantee's lower bound, ∣M∣≤OPT|M| \le \mathrm{OPT}, to tell how close the heuristic's answer must be.

4. Solve it exactly anyway, cleverly

Exponential does not mean hopeless. The Held–Karp dynamic programme solves TSP in O(n22n)O(n^2 2^n) time instead of trying all (n−1)!/2(n-1)!/2 tours, the subset version of the ideas in Dynamic programming. Branch and bound explores a search tree but prunes any branch whose lower bound already exceeds the best solution found.

python
import math, random

rng = random.Random(7)
n = 12
pts = [(rng.uniform(0, 100), rng.uniform(0, 100)) for _ in range(n)]
d = [[math.dist(p, q) for q in pts] for p in pts]

def length(tour):
    return sum(d[tour[i]][tour[(i + 1) % len(tour)]] for i in range(len(tour)))

def nearest_neighbour(start=0):
    tour, left = [start], set(range(n)) - {start}
    while left:
        nxt = min(left, key=lambda j: d[tour[-1]][j])
        tour.append(nxt)
        left.remove(nxt)
    return tour

def two_opt(tour):
    """Local search: reverse a segment whenever that shortens the tour; stop at a local optimum."""
    tour, improved = tour[:], True
    while improved:
        improved = False
        for i in range(1, n - 1):
            for j in range(i + 1, n):
                a, b, c, e = tour[i - 1], tour[i], tour[j], tour[(j + 1) % n]
                if d[a][c] + d[b][e] < d[a][b] + d[c][e] - 1e-12:
                    tour[i:j + 1] = reversed(tour[i:j + 1])
                    improved = True
    return tour

def held_karp():
    """Exact dynamic programme over subsets: O(n^2 2^n) time instead of (n-1)! tours."""
    best = {(1, 0): 0.0}          # (visited cities as a bitmask, last city) -> shortest path from city 0
    for mask in range(1, 1 << n):
        if not mask & 1:
            continue
        for last in range(n):
            if (mask, last) not in best:
                continue
            for nxt in range(n):
                if mask & (1 << nxt):
                    continue
                key = (mask | (1 << nxt), nxt)
                cand = best[mask, last] + d[last][nxt]
                if cand < best.get(key, math.inf):
                    best[key] = cand
    full = (1 << n) - 1
    return min(best[full, last] + d[last][0] for last in range(1, n))

nn = nearest_neighbour()
opt2 = two_opt(nn)
exact = held_karp()
print(f"nearest neighbour:   {length(nn):6.1f}  ({length(nn) / exact - 1:+.1%} vs optimum)")
print(f"after 2-opt:         {length(opt2):6.1f}  ({length(opt2) / exact - 1:+.1%} vs optimum)")
print(f"optimum (Held-Karp): {exact:6.1f}")
print(f"brute force would check {math.factorial(n - 1) // 2:,} distinct tours")
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

On this instance 2-opt happens to reach the optimum; on larger ones it typically lands within a few per cent. The state of the art combines everything: the Concorde solver, using linear-programming bounds and branch-and-cut, has found and proved optimal a tour through 85,900 points arising from a chip-manufacturing problem.

5. Hand it to a solver

For most engineers, coping means modelling. You describe the problem in a solver's language and let decades of engineering do the search.

  • SAT solvers (MiniSat, CaDiCaL, Kissat and others, compared yearly at the SAT Competition) routinely solve industrial formulas with millions of clauses. They verify hardware designs, find bugs in software by bounded model checking, schedule, and resolve package dependencies: libsolv, which several Linux distributions' package managers use, is a SAT-based resolver.
  • Integer linear programming (ILP) solvers (HiGHS and SCIP, which are open source, and commercial ones such as Gurobi and CPLEX) minimise a linear objective subject to linear constraints with integer variables. Airline crew scheduling, vehicle routing, power-grid planning and chip floor-planning are solved this way every day.
  • Constraint programming tools, such as the CP-SAT solver in Google's OR-Tools, combine both styles.

The skill is in the model: choosing variables and constraints so that the solver's propagation and bounds are strong. A worst case that is exponential in theory may never appear in your data.

Optional Christian reflection · Knowing your limits

A reflection from the Christian tradition that inspires Lumenary Academy. It is not part of the mathematics and you are welcome to skip it.

There is a kind of freedom in an impossibility result. An engineer who has proved her scheduling problem NP-hard has not failed; she has learned the shape of the ground she stands on, and can now spend her effort where it will bear fruit, on good-enough answers, honest bounds and the structure of the real data. Many traditions, Christianity among them, treat knowing one's limits as the beginning of wisdom rather than its end. The mathematics here is the same for every reader; what you make of a limit is your own.

Common misconceptionsH

Common misconceptions

Misconception

"NP stands for non-polynomial." It stands for nondeterministic polynomial. Every problem in P is also in NP. "NP-hard" is the phrase for "at least as hard as everything in NP".

Misconception

"NP-complete means it cannot be solved in practice." It means no known algorithm is polynomial on every input. SAT solvers handle huge real formulas; Concorde solves TSP instances with tens of thousands of cities exactly. Conversely, a small but nasty instance can defeat any solver.

Misconception

"To show my problem is hard, I reduce it to SAT." That is backwards: it shows SAT can express your problem. To show hardness, reduce a known NP-hard problem to yours.

Misconception

"Quantum computers will solve NP-complete problems." No efficient quantum algorithm for any NP-complete problem is known, and most researchers believe none exists. Grover's search gives only a square-root speed-up over brute force, which turns 2n2^n into 2n/22^{n/2}: still exponential.

Misconception

"An exponential algorithm is always worse than a polynomial one." Asymptotically, yes. For the sizes you actually have, 1.001n1.001^n beats n4n^4 until nn is in the tens of thousands. Measure on real inputs.

Exercises

Exercises

1. Hard problems: P, NP and coping

Warm-upHuman

Which of these are decision problems in the sense of the lesson? Select all that apply.

Choose all that apply

2. Hard problems: P, NP and coping

CoreHuman

Assume only what is currently known (P versus NP is open). Which statements are true? Select all that apply.

Choose all that apply

3. Hard problems: P, NP and coping

CoreHuman

You suspect that your new problem EXAM-SLOTS (assigning exams to time slots with constraints) is NP-hard. Which argument proves it?

Choose one

4. Hard problems: P, NP and coping

Warm-upComputational

Write the NP verifier for SAT. satisfies(clauses, assignment) receives a CNF formula as a list of clauses, each a list of nonzero integers (3 means x3x_3, -3 means ¬x3\lnot x_3), and a dictionary mapping each variable number to True or False. Return True exactly when every clause contains at least one literal made true by the assignment. An empty clause can never be satisfied; an empty formula (no clauses) is always satisfied.

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

5. Hard problems: P, NP and coping

CoreHuman

Using the lesson's reduction from kk-colouring to SAT (at least one colour per vertex, at most one colour per vertex, neighbours differ), how many clauses does the formula have for a graph with 5 vertices and 7 edges when k=3k = 3?

6. Hard problems: P, NP and coping

Warm-upHuman

You run the lesson's matching algorithm for vertex cover on a large graph, and it returns a cover of 18 vertices. What is the smallest the optimal vertex cover could possibly be?

7. Hard problems: P, NP and coping

CoreComputational

Implement approx_vertex_cover(edges), the 2-approximation from the lesson. edges is a list of pairs (u, v). Return a set of vertices that covers every edge and has at most twice as many vertices as the smallest cover. (The tests compare against a brute-force optimum on small random graphs.)

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

8. Hard problems: P, NP and coping

StretchComputational

Coping by parameter: write has_cover(edges, k) that returns True exactly when the graph has a vertex cover of at most k vertices. Use the branching idea from the lesson: if there are no edges, the answer is yes; if k == 0 and edges remain, no; otherwise pick any edge (u, v); one of u or v must be in the cover, so try both (remove every edge touching the chosen vertex and recurse with k - 1). This takes O(2k⋅m)O(2^k \cdot m) time, fast for small k even on big graphs.

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

Further reading and resources