Time Complexity: P and NP

Complexity theory works with decision problems: computational problems whose answer is YES or NO. This is not a restriction — optimization problems can be recast as decision problems ("Is there a tour of length ≤ k?"), and the decision version is at least as hard as the optimization version up to a polynomial.

Formally, a decision problem is a language L ⊆ Σ* — a set of strings over some alphabet Σ. An instance x ∈ Σ* is a YES-instance if x ∈ L, and a NO-instance otherwise. The problem of determining membership is the computational task.

Example: GRAPH-3-COLORABILITY is the language of all graph encodings ⟨G⟩ such that G is 3-colorable. The alphabet is {0,1}; a graph is encoded as an adjacency matrix or edge list; the language contains exactly those encodings of graphs that admit a proper 3-coloring.

This encoding view is important: the complexity of a problem can depend on the encoding. In practice, all "reasonable" encodings of the same combinatorial object are polynomially related (converting between them costs polynomial time), so the complexity class a problem belongs to is encoding-independent for reasonable encodings.

Why decision problems? They are the simplest non-trivial output (one bit), making the theory cleaner. The Turing machine model (and the RAM model) both handle decision problems naturally, and the theory extends smoothly to function problems via search-to-decision reductions.

# Encoding a graph as an adjacency-matrix bitstring (concrete example)
# Vertices: 0..n-1. Entry (i,j) is 1 if edge exists.

def encode_graph(n: int, edges: list[tuple[int,int]]) -> str:
    """Returns a binary string encoding of the graph."""
    matrix = [[0]*n for _ in range(n)]
    for u, v in edges:
        matrix[u][v] = matrix[v][u] = 1
    bits = ''.join(str(matrix[i][j])
                   for i in range(n) for j in range(n))
    return f"{n}#{bits}"  # prefix with n so decoding is unambiguous

# This is a YES-instance of GRAPH-3-COLORABILITY:
# Triangle (K3) needs 3 colors, uses exactly 3.
print(encode_graph(3, [(0,1),(1,2),(0,2)]))
# K4 (complete on 4 vertices) requires 4 colors => NO-instance
print(encode_graph(4, [(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)]))

The time complexity of an algorithm on input x is the number of elementary steps it takes as a function of |x|, the length of x. We usually express this as a worst-case function T(n) where n = |x|.

We use asymptotic notation to focus on growth rate, ignoring constant factors (which depend on hardware, language, etc.):

• T(n) = O(f(n)): T is eventually bounded above by c·f(n) for some constant c > 0.
• T(n) = Ω(f(n)): T is eventually bounded below by c·f(n).
• T(n) = Θ(f(n)): both O and Ω.

Why polynomial vs. exponential? A polynomial-time algorithm with T(n) = n^100 sounds slow, but the key insight (Cobham's thesis, 1965) is that for any fixed polynomial p, and any fixed exponential base b > 1, p(n) grows slower than b^n for large enough n. Moreover, polynomial running times compose: if step A takes n^2 steps and calls step B which takes n^3 steps, the whole thing takes n^5 steps — still polynomial. Exponential algorithms on input of size n = 300 take longer than the age of the universe even at 10^12 operations/second.

The formal model: A deterministic Turing machine M decides language L in time T(n) if for every input x of length n, M halts in at most T(n) steps and accepts iff x ∈ L. The choice of model (TM vs. RAM vs. word RAM) changes T(n) by at most a polynomial factor — so polynomial-time decidability is model-independent.

# Illustration: polynomial vs. exponential growth
import math

def show_growth(n_values):
    print(f"{'n':>6} {'n^3':>12} {'2^n':>20}")
    for n in n_values:
        poly = n**3
        # 2^n overflows quickly; show symbolically above n=100
        exp_str = str(2**n) if n <= 60 else f"~10^{int(n*math.log10(2))}"
        print(f"{n:>6} {poly:>12} {exp_str:>20}")

show_growth([10, 20, 50, 100, 300])
# n=300: n^3 = 27,000,000 (milliseconds on modern hardware)
#         2^300 ~ 10^90 (more than atoms in observable universe)

P (Polynomial time) is the class of all decision problems solvable by a deterministic algorithm in polynomial time:

P = { L : there exists a TM M and polynomial p such that M decides L and for all inputs x, M halts in at most p(|x|) steps }

Informally: P is the class of problems we can solve efficiently.

Representative problems in P:

• REACHABILITY: Given a directed graph G and vertices s, t, is there a path from s to t? (BFS/DFS, O(V+E))
• SORTING: Is array A sorted? (O(n)). Sorting itself: O(n log n).
• PRIMALITY: Is integer n prime? (AKS algorithm, 2002, O(log^6 n) — a landmark result)
• LINEAR PROGRAMMING: Is there a feasible point for a linear program? (Ellipsoid method, polynomial; simplex is practical but exponential worst-case)
• BIPARTITE MATCHING: Does a bipartite graph have a perfect matching? (O(E√V))
• SHORTEST PATHS: Dijkstra's algorithm, O((V+E) log V) with a heap.

P is closed under complement, union, intersection, and polynomial-time reductions — it is a robust class. Problems in P are considered "tractable" in the theoretical sense, though a practical engineer also cares about the degree of the polynomial and the hidden constants.

Philosophical note: P captures an idealization. An O(n^1000) algorithm is technically in P but useless in practice. The remarkable empirical fact is that almost all natural problems in P have small-degree polynomial algorithms (O(n), O(n log n), O(n^2), O(n^3)).

# Two P-problems side by side
from collections import deque

# REACHABILITY in O(V+E) -- a P-problem
def reachable(graph: dict[int, list[int]], s: int, t: int) -> bool:
    """BFS: is t reachable from s?"""
    visited = {s}
    queue = deque([s])
    while queue:
        u = queue.popleft()
        if u == t:
            return True
        for v in graph[u]:
            if v not in visited:
                visited.add(v)
                queue.append(v)
    return False

# PRIMALITY TEST (Miller-Rabin, probabilistic; deterministic AKS exists)
def miller_rabin(n: int, a: int) -> bool:
    """Returns False if n is composite (witness a), True if probably prime."""
    if n % 2 == 0:
        return n == 2
    d, r = n - 1, 0
    while d % 2 == 0:
        d //= 2
        r += 1
    x = pow(a, d, n)          # fast modular exponentiation
    if x in (1, n - 1):
        return True
    for _ in range(r - 1):
        x = x * x % n
        if x == n - 1:
            return True
    return False

def is_prime(n: int) -> bool:
    for a in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]:
        if n == a: return True
        if not miller_rabin(n, a): return False
    return True

NP (Nondeterministic Polynomial time) is most cleanly defined via polynomial-time verifiers, not nondeterminism (though the two are equivalent).

Definition (verifier): A language L ∈ NP if and only if there exists a polynomial-time algorithm V (the verifier) and a polynomial p such that:

x ∈ L ⟺ ∃ certificate c with |c| ≤ p(|x|) and V(x, c) = 1

V takes the input x and a proposed certificate (also called a witness or proof) c, and accepts iff c is a valid proof that x ∈ L.

Key intuition: NP is the class of problems where "YES" answers have short, efficiently checkable proofs. The verifier is honest — it doesn't cheat. The certificate is a succinct hint that lets a polynomial-time algorithm confirm the answer.

Examples:

• 3-SAT: Instance = Boolean formula in CNF with 3 literals/clause. Certificate = a satisfying assignment. Verification: substitute and check all clauses — O(n).
• HAMILTONIAN-CYCLE: Instance = graph G. Certificate = a permutation of vertices claiming to be a Hamiltonian cycle. Verification: check it visits every vertex exactly once and each consecutive pair is an edge — O(n).
• GRAPH-3-COLORABILITY: Certificate = an assignment of colors {1,2,3} to vertices. Verification: check every edge has endpoints of different colors — O(E).
• SUBSET-SUM: Instance = set S of integers and target t. Certificate = the subset. Verification: sum it up — O(n).

Nondeterministic Turing machine (NTM) equivalence: An NTM can branch into multiple computational paths simultaneously. A language is in NP iff it is decided by a polynomial-time NTM — the machine guesses the certificate and verifies it. This is why it is called Nondeterministic Polynomial.

NP contains P: Any problem in P is also in NP — just use an empty certificate and let V run the P-algorithm itself.

co-NP: The complement class: L ∈ co-NP if NO-instances have short, efficiently checkable proofs. TAUTOLOGY ("is this Boolean formula always true?") is in co-NP. Whether NP = co-NP is another major open problem.

# NP verifier for 3-SAT
# Input: CNF formula (list of 3-literal clauses) + assignment (certificate)
# A clause is a list of literals; literal i means variable i+1 is True,
# literal ~i means variable i+1 is False (0-indexed variables).

def verify_3sat(clauses: list[list[int]], assignment: dict[int, bool]) -> bool:
    """
    Polynomial-time verifier for 3-SAT.
    clauses: list of [lit, lit, lit] where positive int = var, negative = negation
    assignment: {var_index: True/False}
    Returns True iff the assignment satisfies ALL clauses.
    """
    for clause in clauses:
        satisfied = False
        for lit in clause:
            var = abs(lit)
            val = assignment[var]
            if (lit > 0 and val) or (lit < 0 and not val):
                satisfied = True
                break
        if not satisfied:
            return False   # this clause is falsified
    return True

# Example: (x1 OR x2 OR ~x3) AND (~x1 OR x3 OR x4) AND (~x2 OR ~x3 OR ~x4)
clauses = [[1, 2, -3], [-1, 3, 4], [-2, -3, -4]]
assignment = {1: True, 2: False, 3: False, 4: True}
print(verify_3sat(clauses, assignment))  # True — valid certificate!

# Key point: this verifier runs in O(n) — polynomial in the input size.
# Finding the assignment is hard (NP-hard); checking it is easy (P).

A polynomial-time many-one reduction (Karp reduction) from problem A to problem B is a function f computable in polynomial time such that:

x ∈ A ⟺ f(x) ∈ B

We write A ≤_p B ("A reduces to B in polynomial time" or "A is polynomial-time reducible to B").

Intuitive meaning: If we had an efficient algorithm for B, we could use it to solve A efficiently — just transform the A-instance to a B-instance and feed it in. So B is at least as hard as A.

Formal consequences:

1. If A ≤_p B and B ∈ P, then A ∈ P.
2. If A ≤_p B and A ∉ P (assuming P ≠ NP), then B ∉ P.
3. Reductions compose: if A ≤_p B and B ≤_p C, then A ≤_p C.

A worked example: 3-COLORING ≤_p SAT

Given graph G = (V, E), construct a SAT formula φ as follows:

• Variables: x_{v,c} for each vertex v and color c ∈ {1,2,3} ("v gets color c")
• Each vertex gets at least one color: ∧v (x{v,1} ∨ x_{v,2} ∨ x_{v,3})
• Each vertex gets at most one color: ∧v ∧{c≠c'} ¬(x_{v,c} ∧ x_{v,c'})
• Adjacent vertices differ: ∧{(u,v)∈E} ∧c ¬(x{u,c} ∧ x{v,c})

This formula is satisfiable iff G is 3-colorable. The construction runs in polynomial time (O(|V| + |E|) clauses). Therefore 3-COLORING ≤_p SAT.

Why reductions are the key tool: They let us build a hardness lattice. Once we know one problem is hard, we can propagate hardness to other problems via reductions, without having to reprove hardness from scratch each time.

# Polynomial-time reduction: INDEPENDENT-SET <=_p CLIQUE
# An independent set in G is a clique in the complement graph G_bar.

def independent_set_to_clique(
    n: int, edges: set[tuple[int,int]], k: int
) -> tuple[int, set[tuple[int,int]], int]:
    """
    Reduces "Does G have an independent set of size k?" to
    "Does G_bar have a clique of size k?"
    
    Returns (n, complement_edges, k) — an equivalent CLIQUE instance.
    This is the identity transformation on k; only the edge set changes.
    """
    all_possible = {
        (min(u,v), max(u,v))
        for u in range(n) for v in range(n) if u != v
    }
    # Normalize input edges
    norm_edges = {(min(u,v), max(u,v)) for u,v in edges}
    complement_edges = all_possible - norm_edges
    return n, complement_edges, k

# Example: Path graph P4 has max independent set of size 2
n = 4
edges = {(0,1),(1,2),(2,3)}
n2, comp, k = independent_set_to_clique(n, edges, 2)
print(f"Complement edges: {comp}")
# Complement of P4 is two edges (0,2),(0,3),(1,3) — check for 2-clique
# (any single edge is a 2-clique, and indeed 0-2 exists)
# => Independent set of size 2 in P4  <=>  Clique of size 2 in comp(P4)  ✓

Definition: A problem B is NP-hard if every problem A ∈ NP reduces to B in polynomial time:

B is NP-hard ⟺ ∀A ∈ NP: A ≤_p B

Informally: B is at least as hard as every problem in NP. Solving B efficiently would let you solve everything in NP efficiently.

Definition: B is NP-complete if B is both NP-hard AND B ∈ NP.

NP-complete problems are the "hardest" problems in NP — they sit at the very top of the NP difficulty hierarchy. There are thousands of natural NP-complete problems across combinatorics, logic, graph theory, scheduling, biology, physics, and economics.

Consequences:

1. If any NP-complete problem is in P, then P = NP.
2. If P ≠ NP (widely believed), then no NP-complete problem has a polynomial-time algorithm.
3. To show B is NP-complete: (a) show B ∈ NP (exhibit a polynomial-time verifier), and (b) show B is NP-hard by reducing some known NP-complete problem to B.

The first NP-complete problem — Cook-Levin Theorem (1971):

SAT (Boolean Satisfiability) is NP-complete.

Cook (and independently Levin) proved that every NP problem can be reduced to SAT. The proof encodes the computation of an NTM as a Boolean formula — each bit of the TM's configuration at each time step becomes a Boolean variable, and the transition rules become clauses. This was the first NP-completeness proof, and it established the template for all subsequent ones.

Karp's 21 problems (1972): Karp immediately showed 21 famous combinatorial problems are NP-complete by reduction from SAT/3-SAT, including CLIQUE, VERTEX-COVER, SET-COVER, HAMILTONIAN-CYCLE, TSP, SUBSET-SUM, and GRAPH-COLORING. This paper launched the modern theory of NP-completeness.

# Sketch: NP-completeness proof structure for CLIQUE
# Part 1: CLIQUE is in NP (verifier)
def verify_clique(adj: list[list[int]], subset: list[int]) -> bool:
    """O(k^2) verifier: check every pair in subset is connected."""
    for i in range(len(subset)):
        for j in range(i+1, len(subset)):
            u, v = subset[i], subset[j]
            if not adj[u][v]:
                return False  # missing edge — not a clique
    return True

# Part 2: 3-SAT <=_p CLIQUE (Karp's reduction, sketched)
# Given a 3-CNF formula with m clauses, build graph G:
#   - One node per (clause, literal) pair => 3m nodes
#   - Add edge between (i, lit_a) and (j, lit_b) if:
#     * i != j  (different clauses)
#     * lit_a and lit_b are not complementary (x and ~x)
# Then: formula is satisfiable  <=>  G has a clique of size m
# (pick one satisfied literal per clause; they form a clique)
def three_sat_to_clique(clauses: list[list[int]]):
    m = len(clauses)
    nodes = [(i, j) for i, clause in enumerate(clauses)
             for j, lit in enumerate(clause)]
    node_idx = {node: idx for idx, node in enumerate(nodes)}
    n = len(nodes)
    adj = [[0]*n for _ in range(n)]
    for (i, a) in nodes:
        for (j, b) in nodes:
            if i == j: continue
            lit_a = clauses[i][a]
            lit_b = clauses[j][b]
            if lit_a != -lit_b:   # not complementary
                u, v = node_idx[(i,a)], node_idx[(j,b)]
                adj[u][v] = adj[v][u] = 1
    return adj, n, m   # CLIQUE instance: does adj have a clique of size m?

P ⊆ NP — this is easy to prove. Any problem in P is in NP: the certificate is empty, and the verifier just runs the P-algorithm.

The open question is whether the containment is strict: is there a problem in NP that is NOT in P? Nobody knows.

Two possible worlds:

World 1: P = NP. Every problem with a polynomial-time checkable proof of YES also has a polynomial-time algorithm to find such a proof. Consequences: RSA and all public-key cryptography based on factoring/DLP collapse. Protein folding becomes tractable. Mathematical proof-finding becomes automatable. Essentially: creativity and verification become equivalent. Most researchers believe this world does NOT exist.

World 2: P ≠ NP. There is a genuine complexity gap — finding is harder than checking. Modern cryptography rests on this assumption. NP-complete problems require exponential time in the worst case. This is the world almost everyone believes we live in, but nobody has proven it.

Why is it so hard to prove P ≠ NP? Three major barriers have been identified:

1. Relativization (Baker-Gill-Solovay, 1975): There exist oracles A and B such that P^A = NP^A but P^B ≠ NP^B. This means any proof technique that "relativizes" (works with arbitrary oracles) cannot resolve P vs NP. This rules out most diagonalization arguments.
2. Natural Proofs (Razborov-Rudich, 1994): Most circuit lower-bound proof strategies can be turned into pseudorandom generator breaks, implying they cannot prove super-polynomial lower bounds against circuits (assuming one-way functions exist). This rules out large families of combinatorial techniques.
3. Algebrization (Aaronson-Wigderson, 2009): Even algebraic extensions of diagonalization cannot work.

What IS known:

• P ≠ PSPACE (proven: there are problems harder than P that don't need superpolynomial time — they need superpolynomial space)
• NP ≠ EXPTIME (proven: exponential time is strictly more powerful than polynomial time)
• The polynomial hierarchy (PH) — an infinite tower of complexity classes between P and PSPACE — collapses to P if P = NP

The $1,000,000 question: The Clay Mathematics Institute lists P vs NP as one of its seven Millennium Prize Problems. A correct proof in either direction wins the prize and transforms computer science, mathematics, and arguably all of human civilization.

# Illustration of the P vs NP gap via SUBSET-SUM
# Checking a certificate is trivially polynomial;
# the best known exact algorithm is exponential.

# NP SIDE: O(n) verifier
def verify_subset_sum(numbers: list[int], target: int,
                     certificate: list[int]) -> bool:
    """Certificate is a subset (list of indices). O(n) check."""
    return sum(numbers[i] for i in certificate) == target

# P SIDE: Dynamic programming — O(n * target) pseudopolynomial,
# NOT polynomial in input length (target needs log(target) bits to encode,
# so this is exponential in the number of bits of the input!)
def dp_subset_sum(numbers: list[int], target: int) -> bool:
    """O(n*target) DP — pseudopolynomial, not truly polynomial."""
    reachable = {0}
    for x in numbers:
        reachable = reachable | {s + x for s in reachable}
    return target in reachable

# The gap: for 'numbers' with 300 large integers,
# the verifier runs in microseconds given a certificate;
# all known exact solvers require exponential time in the worst case.
numbers = [2**i for i in range(30)]  # 30 powers of 2
target = 2**30 - 1                   # all of them
certificate = list(range(30))        # the whole set
print(verify_subset_sum(numbers, target, certificate))  # True, instantly

The class NP is not monolithic. Ladner's theorem (1975) shows that if P ≠ NP, there exist problems in NP that are neither in P nor NP-complete. These are called NP-intermediate problems. The leading candidate is GRAPH ISOMORPHISM (GI): given two graphs G and H, are they isomorphic? GI is in NP (the isomorphism is the certificate), not known to be NP-complete, and not known to be in P. Babai's quasi-polynomial algorithm (2015, corrected 2017) brought it tantalizingly close to P.

Another candidate: INTEGER FACTORIZATION (as a decision problem). It is in NP ∩ co-NP, which is unusual for NP-complete problems (NP-complete problems are widely believed to not be in co-NP unless NP = co-NP).

The complexity hierarchy above NP:

• co-NP: Problems whose complement is in NP. TAUTOLOGY (is every assignment satisfying?) is co-NP-complete. NP = co-NP is an open question.
• PH (Polynomial Hierarchy): Built from alternating quantifiers. Σ_2^p: "∃x ∀y φ(x,y)" — like ∀∃-SAT. The PH captures problems with multiple levels of nondeterminism.
• PSPACE: All problems solvable with polynomial space (and any amount of time). PSPACE-complete problems include QSAT (Quantified Boolean Formula satisfiability). P ⊆ NP ⊆ PH ⊆ PSPACE ⊆ EXPTIME.
• #P: Counting complexity. Instead of YES/NO, count the number of solutions. #P-complete: count satisfying assignments of a CNF formula. #P is harder than NP in a precise sense.

Key inclusion chain (all proven):

P ⊆ NP ⊆ PSPACE ⊆ EXPTIME

And P ≠ EXPTIME is proven (by the time hierarchy theorem), but where exactly the separations within this chain occur is mostly open.

# GRAPH ISOMORPHISM -- the famous NP-intermediate candidate
# Certificate: a bijection between vertex sets
def verify_graph_isomorphism(
    adj1: list[list[int]],   # adjacency matrix of G1
    adj2: list[list[int]],   # adjacency matrix of G2
    mapping: list[int]       # certificate: mapping[i] = image of vertex i in G2
) -> bool:
    """O(n^2) verifier: check that mapping is an isomorphism."""
    n = len(adj1)
    if sorted(mapping) != list(range(n)):
        return False  # not a bijection
    for i in range(n):
        for j in range(n):
            if adj1[i][j] != adj2[mapping[i]][mapping[j]]:
                return False
    return True

# Two isomorphic graphs: cycle C4 labelled differently
adj1 = [[0,1,0,1],[1,0,1,0],[0,1,0,1],[1,0,1,0]]  # 0-1-2-3-0
adj2 = [[0,1,1,0],[1,0,0,1],[1,0,0,1],[0,1,1,0]]  # 0-1-3-2-0 relabelled
mapping = [0, 2, 1, 3]   # proposed isomorphism
print(verify_graph_isomorphism(adj1, adj2, mapping))  # True

# Finding this mapping is the hard part — no polynomial algorithm is known,
# but none has been ruled out either (NP-intermediate status)

NP-completeness is a worst-case, exact statement. Real-world problem-solving has many escape hatches:

1. Approximation algorithms. For optimization versions of NP-hard problems, find a solution whose value is within a constant factor (or (1+ε)) of optimal. The celebrated MAX-CUT approximation (Goemans-Williamson, 1995) achieves a 0.878-approximation via semidefinite programming. VERTEX-COVER has a simple 2-approximation. The inapproximability results (from the PCP Theorem, 1992) show that some NP-hard problems cannot be approximated beyond a certain factor unless P = NP — for example, MAX-CLIQUE cannot be approximated to within n^{1-ε} for any ε > 0.

2. Fixed-parameter tractability (FPT). Many NP-hard problems are tractable when a certain parameter k is small. VERTEX-COVER is solvable in O(2^k · n) — exponential only in k (the cover size), polynomial in n. If k is small (e.g., k ≤ 50), this is practical. The field of parameterized complexity studies which parameters make which problems tractable.

3. Exact algorithms for special structure. Dynamic programming on tree decompositions (treewidth), branch-and-bound with strong pruning, cutting-plane methods in integer programming — these work well on structured instances that arise in practice, even if the worst case is exponential.

4. Heuristics and metaheuristics. Simulated annealing, genetic algorithms, local search, and MCTS find good (not optimal) solutions quickly. No worst-case guarantees, but empirically effective.

5. Average-case tractability. Some NP-hard problems are easy on random instances. Random 3-SAT is easy below the satisfiability threshold. The planted clique problem is hard in the worst case but has polynomial algorithms for most instances.

Knowing a problem is NP-complete guides the engineer to the right toolbox immediately, without wasting time searching for an exact polynomial algorithm that does not exist (assuming P ≠ NP).

# Approximation algorithm: 2-approximation for VERTEX COVER
# The algorithm: repeatedly pick any uncovered edge, add BOTH endpoints.
# This never needs more than 2x the optimal cover.

def vertex_cover_2approx(n: int, edges: list[tuple[int,int]]) -> set[int]:
    """
    Greedy 2-approximation for minimum vertex cover.
    Theorem: |output| <= 2 * OPT (can be proven via a matching lower bound).
    """
    cover = set()
    uncovered = list(edges)
    while uncovered:
        u, v = uncovered.pop()         # pick any edge
        cover.add(u)
        cover.add(v)
        # Remove all edges now covered
        uncovered = [(a,b) for (a,b) in uncovered
                     if a not in cover and b not in cover]
    return cover

# Verify it covers all edges
def is_vertex_cover(n, edges, cover):
    return all(u in cover or v in cover for u,v in edges)

edges = [(0,1),(0,2),(1,3),(2,3),(3,4)]
cover = vertex_cover_2approx(5, edges)
print(cover)                              # e.g. {0, 1, 2, 3}
print(is_vertex_cover(5, edges, cover))   # True
# OPT = 2 (vertices 0 and 3 cover everything); our approx = 4 (within 2x)