"""Brute-force checks of five constructions of the paper on small random instances: 1. the perceptron gadget (Lemma 3.3); 2. the width-reduction transfer (Lemma 3.5); 3. OR-chains with copying (Lemma 5.4); 4. hypergraph k-coloring to k-term DNF consistency for k = 2, after Pitt and Valiant (Proposition F.1); 5. CNF satisfiability to hypergraph k-coloring for k = 2, 3 (Proposition F.1). Each part prints a line ending in OK when all of its assertions hold. Usage: python check_reductions.py """ import itertools, random def rand_cnf(N, m, kmin, kmax, rng): """At most m distinct random clauses (fewer when N admits fewer).""" F = set() for _ in range(100 * m): if len(F) >= m: break r = rng.randint(kmin, kmax) vs = rng.sample(range(N), r) F.add(frozenset((v, rng.choice([True, False])) for v in vs)) # (var, positive?) return [sorted(c) for c in F] def sat(z, C): return any(z[v] == pos for v, pos in C) def count(F, N): return sum(all(sat(z, C) for C in F) for z in itertools.product([False, True], repeat=N)) # ---------- 1. perceptron gadget ---------- def gadget(F, N, k): p = max(1, k - 2) S = [] for j in range(p): x = [0] * (N + p); x[N + j] = 1; S.append(x) for C in F: r = len(C); x = [0] * (N + p) for v, pos in C: x[v] = 1 if pos else -1 if r >= 2: for j in range(r - 2): x[N + j] = 1 else: x[N] = -1 assert sum(1 for a in x if a) <= max(2 * k - 2, 2) S.append(x) return S, p def check_gadget(trials=200): rng = random.Random(1) for _ in range(trials): k = rng.randint(1, 4); N = rng.randint(1, 6); m = rng.randint(1, 8) try: F = rand_cnf(N, m, 1, min(k, N), rng) except Exception: continue S, p = gadget(F, N, k) vs = 0 for sig in itertools.product([-1, 1], repeat=N + p): if all(sum(a * b for a, b in zip(sig, x)) >= 0 for x in S): vs += 1 assert vs == count(F, N), (F, N, k, vs, count(F, N)) print("gadget OK") # ---------- 2. width reduction ---------- def simplify(F, assign): out = [] for C in F: newC = []; satisfied = False for v, pos in C: if v in assign: if assign[v] == pos: satisfied = True; break else: newC.append((v, pos)) if satisfied: continue out.append(tuple(newC)) return out def reduce_k(F, k, free, leaves, path): if any(len(C) == 0 for C in F): return long = [C for C in F if len(C) > k] if not long: leaves.append((F, set(free), path)); return C = long[0]; Cp = C[:k] FL = [D for D in F if D != C] + [Cp] # dedupe FL = list(dict.fromkeys(FL)) reduce_k(FL, k, free, leaves, path + 'L') assign = {v: (not pos) for v, pos in Cp} FR = list(dict.fromkeys(simplify(F, assign))) reduce_k(FR, k, free - set(assign), leaves, path + 'R') def count_free(F, free): free = sorted(free); tot = 0 for bits in itertools.product([False, True], repeat=len(free)): z = dict(zip(free, bits)) if all(any(z[v] == pos for v, pos in C) for C in F): tot += 1 return tot def check_widthred(trials=150): rng = random.Random(2) from math import comb for _ in range(trials): N = rng.randint(3, 9); m = rng.randint(1, 7); k = rng.randint(1, 3) F = [tuple(c) for c in rand_cnf(N, m, 1, N, rng)] m = len(F) leaves = [] reduce_k(F, k, set(range(N)), leaves, '') total = sum(count_free(L, fr) for L, fr, _ in leaves) assert total == count(F, N), (F, total, count(F, N)) for L, fr, path in leaves: r = path.count('R'); l = path.count('L') assert l <= m and r <= N // k and len(fr) <= N - k * r assert all(len(C) <= k for C in L) # leaf count bound byr = {} for _, _, path in leaves: byr[path.count('R')] = byr.get(path.count('R'), 0) + 1 for r, c in byr.items(): assert c <= comb(m + r, r) print("width reduction OK") # ---------- 3. chain lemma ---------- def check_chain(trials=40): rng = random.Random(3) for _ in range(trials): N = rng.randint(1, 3); m = rng.randint(1, 2) F = rand_cnf(N, m, 1, min(3, N), rng) # build factor graph var = 0; names = {} def new(name): nonlocal var; names[var] = name; var += 1; return var - 1 cur = {i: new(('z', i, 0)) for i in range(N)} factors = []; bags = [] for j, C in enumerate(F): c_prev = new(('c', j, 0)); factors.append(((c_prev,), lambda a: a[0] == 0)) first = True for t, (v, pos) in enumerate(C, 1): zn = new(('z', v, (j, t))); ct = new(('c', j, t)) old = cur[v] factors.append(((zn, old), lambda a: a[0] == a[1])) factors.append(((ct, c_prev, zn), (lambda pos: lambda a: a[0] == (a[1] or (a[2] == (1 if pos else 0))))(pos))) bag = set(cur.values()) | {zn, c_prev, ct} bags.append(bag) cur[v] = zn; c_prev = ct factors.append(((c_prev,), lambda a: a[0] == 1)) n = var Z = 0 for x in itertools.product([0, 1], repeat=n): if all(f(tuple(x[i] for i in sc)) for sc, f in factors): Z += 1 assert Z == count(F, N), (Z, count(F, N)) deg = [0] * n for sc, _ in factors: for i in sc: deg[i] += 1 assert max(deg) <= 3 assert max(len(b) for b in bags) <= N + 3 for sc, _ in factors: assert any(set(sc) <= b for b in bags), sc for v in range(n): idx = [i for i, b in enumerate(bags) if v in b] if idx: assert idx == list(range(idx[0], idx[-1] + 1)), (v, idx) print("chain OK") # ---------- 4. hypergraph coloring -> k-term DNF (Pitt-Valiant) ---------- def check_pv(trials=60): rng = random.Random(4) for _ in range(trials): n = rng.randint(2, 5); k = 2 E = set() for _ in range(rng.randint(1, 4)): r = rng.randint(2, n); E.add(frozenset(rng.sample(range(n), r))) colorable = any(all(len({col[u] for u in S}) > 1 for S in E) for col in itertools.product(range(k), repeat=n)) pos = [tuple(0 if i == u else 1 for i in range(n)) for u in range(n)] neg = [tuple(0 if i in S else 1 for i in range(n)) for S in E] terms = list(itertools.product([0, 1, 2], repeat=n)) # 0 absent,1 x_i,2 not x_i def ev(T, x): return all((t == 0) or (t == 1 and x[i] == 1) or (t == 2 and x[i] == 0) for i, t in enumerate(T)) acc = {T: (tuple(ev(T, x) for x in pos), tuple(ev(T, x) for x in neg)) for T in terms} good = [T for T in terms if not any(acc[T][1])] consistent = any(all(acc[T1][0][i] or acc[T2][0][i] for i in range(n)) for T1 in good for T2 in good) assert consistent == colorable, (n, E, consistent, colorable) print("Pitt-Valiant OK") def check_cnf_to_coloring(trials=60): rng = random.Random(5) for _ in range(trials): N = rng.randint(1, 3); m = rng.randint(1, 4); k = rng.choice([2, 3]) F = rand_cnf(N, m, 1, N, rng) U = [('z', i, True) for i in range(N)] + [('z', i, False) for i in range(N)] + [('bot',)] + [('s', a) for a in range(k - 2)] idx = {u: t for t, u in enumerate(U)} E = [{idx[('z', i, True)], idx[('z', i, False)]} for i in range(N)] E += [{idx[('z', v, pos)] for v, pos in C} | {idx[('bot',)]} for C in F] S = [idx[('s', a)] for a in range(k - 2)] E += [{a, b} for a in S for b in S if a < b] E += [{a, u} for a in S for u in range(len(U)) if u not in S] colorable = any(all(len({col[u] for u in e}) > 1 for e in E) for col in itertools.product(range(k), repeat=len(U))) assert colorable == (count(F, N) > 0) print("CNF -> coloring OK") if __name__ == '__main__': check_gadget(); check_widthred(); check_chain(); check_pv(); check_cnf_to_coloring()