Complexity theory & NP

import itertools

def verify_subset_sum(numbers, target, certificate):
    """A VERIFIER for subset-sum: given a proposed subset (the 'certificate'),
    check it in polynomial time. Fast verification is the essence of NP."""
    if not set(certificate).issubset(set(range(len(numbers)))):
        return False
    return sum(numbers[i] for i in certificate) == target

def solve_subset_sum_bruteforce(numbers, target):
    """FINDING the certificate is the hard part: 2^n subsets to try."""
    for r in range(len(numbers) + 1):
        for combo in itertools.combinations(range(len(numbers)), r):
            if sum(numbers[i] for i in combo) == target:
                return list(combo)
    return None

nums = [3, 34, 4, 12, 5, 2]
target = 9
cert = solve_subset_sum_bruteforce(nums, target)      # slow: explores 2^n
print("found subset indices :", cert)                 # e.g. [2, 4] -> 4+5=9
print("verifies?            :", verify_subset_sum(nums, target, cert))  # True
print("bogus cert verifies? :", verify_subset_sum(nums, target, [0, 1]))  # False

import itertools

def three_sat_to_clique(clauses):
    """Reduce 3-SAT to CLIQUE (the textbook Karp reduction).

    Build a graph with one vertex per literal-occurrence. Connect two vertices
    if they are in DIFFERENT clauses AND are not contradictory (x and NOT x).
    A satisfying assignment exists  <=>  the graph has a clique of size k
    (k = number of clauses): pick one true literal per clause, all mutually
    consistent -> a clique.  literals are ints: 2 means x2, -2 means NOT x2."""
    verts = []                                # (clause_index, literal)
    for ci, clause in enumerate(clauses):
        for lit in clause:
            verts.append((ci, lit))
    edges = set()
    for a, b in itertools.combinations(range(len(verts)), 2):
        (ci, la), (cj, lb) = verts[a], verts[b]
        if ci != cj and la != -lb:            # different clause, not contradictory
            edges.add((a, b))
    return verts, edges

def has_clique(n, edges, k):
    """Brute-force clique check (itself exponential) — used only to CONFIRM the
    reduction is faithful on tiny instances."""
    adj = {i: set() for i in range(n)}
    for a, b in edges:
        adj[a].add(b); adj[b].add(a)
    for combo in itertools.combinations(range(n), k):
        if all(b in adj[a] for a, b in itertools.combinations(combo, 2)):
            return True
    return False

# (x1 OR x2 OR x3) AND (NOT x1 OR x2 OR x3) — satisfiable (e.g. x2=True)
clauses = [[1, 2, 3], [-1, 2, 3]]
verts, edges = three_sat_to_clique(clauses)
k = len(clauses)
print("literal-vertices :", len(verts))
print("has clique of size k=%d :" % k, has_clique(len(verts), edges, k))  # True

def halting_paradox_sketch():
    """The halting problem is UNDECIDABLE: no program can decide, for every
    (program, input) pair, whether it halts. The classic diagonal argument,
    shown as a contradiction (this does NOT run a real 'halts' oracle)."""
    def halts(program, inp):
        raise NotImplementedError("assume this oracle exists, then derive absurdity")

    def paradox(program):
        if halts(program, program):
            while True:                       # if it halts, loop forever
                pass
        else:
            return                            # if it loops, halt

    # Now ask: does paradox(paradox) halt?
    #  - If halts(paradox, paradox) == True  -> paradox loops -> it does NOT halt.
    #  - If halts(paradox, paradox) == False -> paradox halts -> it DOES halt.
    # Both cases contradict the oracle. Therefore 'halts' cannot exist.
    return "No consistent 'halts' oracle can exist — halting is undecidable."

print(halting_paradox_sketch())

import itertools, random

def tsp_bruteforce(dist):
    """Exact travelling-salesman (return to start). O(n!) — only tiny n."""
    n = len(dist)
    best, best_tour = float("inf"), None
    for perm in itertools.permutations(range(1, n)):
        tour = (0,) + perm + (0,)
        cost = sum(dist[tour[i]][tour[i + 1]] for i in range(n))
        if cost < best:
            best, best_tour = cost, tour
    return best, best_tour

def tsp_nearest_neighbour(dist):
    """A greedy HEURISTIC: always go to the nearest unvisited city. O(n^2).
    Fast but NOT optimal — a bounded, practical answer instead of an exact one."""
    n = len(dist)
    unvisited = set(range(1, n))
    tour, cur, cost = [0], 0, 0
    while unvisited:
        nxt = min(unvisited, key=lambda c: dist[cur][c])
        cost += dist[cur][nxt]
        cur = nxt; tour.append(cur); unvisited.discard(cur)
    cost += dist[cur][0]; tour.append(0)
    return cost, tour

random.seed(7)
n = 8
pts = [(random.random(), random.random()) for _ in range(n)]
dist = [[((a[0]-b[0])**2 + (a[1]-b[1])**2) ** 0.5 for b in pts] for a in pts]
exact, _ = tsp_bruteforce(dist)
approx, _ = tsp_nearest_neighbour(dist)
print("exact  cost : %.3f" % exact)
print("greedy cost : %.3f" % approx)
print("greedy within %.1f%% of optimal" % (100 * (approx - exact) / exact))

def vertex_cover_2approx(edges):
    """2-approximation for minimum vertex cover (NP-hard to solve exactly).
    Repeatedly pick any uncovered edge and take BOTH endpoints. The result is
    at most 2x the optimum — a provable guarantee, not just a hope."""
    cover = set()
    remaining = set(map(tuple, (map(lambda e: tuple(sorted(e)), edges))))
    while remaining:
        u, v = next(iter(remaining))
        cover.add(u); cover.add(v)
        remaining = {(a, b) for (a, b) in remaining if a not in (u, v) and b not in (u, v)}
    return cover

edges = [(0, 1), (1, 2), (2, 3), (3, 0), (1, 3)]
cover = vertex_cover_2approx(edges)
covered = all(a in cover or b in cover for a, b in edges)
print("cover      :", sorted(cover))
print("covers all edges :", covered)
print("size <= 2x optimal (guaranteed) :", True)