"""fatehard.py -- deciding an atom's fate encodes SUBSET SUM. QUESTION. A cell is atoms r of mass w_r with a posterior row over k labels; a rule gives atom r its top s_r labels, costing w_r s_r and covering w_r P_r(s_r), P_r(s) the sum of its s largest posteriors; OPT is the least cost covering T. An atom is FORCED-ABANDONED when every optimum gives it s = 0, FORCED-SERVED when none does, OPEN otherwise. At unrestricted masses, is deciding an atom's fate as hard as the rest's knapsack? THE DERIVATION (before code). SUBSET SUM: positive integers b_1..b_n and B; is there a subset summing to exactly B? Build a cell with k = 2: atom i of mass b_i u and row (1, 0); atom a of mass W u, W = B + 3/4, row (p, 1 - p), p = (B + 1/2)/W; u = 1/(sum b + W); T = B u (< 1). Every option of a rest atom costs at least what it covers, so the rest's least cost at coverage v is the least subset sum >= v (units u), an integer. a at s = 1 covers (B + 1/2) u >= T at cost W u alone. YES (a subset hits B): OPT <= B u, and every rule serving a costs >= W u > B u: a is forced-abandoned, margin 3/4. NO: every rule without a costs >= (B + 1) u > W u >= OPT: a is forced-served, margin at least 1/4. So "is a forced-abandoned?" is NP-hard and "is a forced-served?" is coNP-hard, the masses written in binary. The hardness is weak: on a fixed mass grid every cost s w_r lies on the grid, so the most coverage at each cost is a table over polynomially many costs. THE ENGINE. fates() enumerates every rule of a cell (each atom at each s = 0..k) in exact rationals and reads each atom's fate off the optima; it knows nothing of the reduction. Scaled by 4u every mass and coverage of a reduction cell is an integer, which the engine is also handed, as a second path the control reads. PREDICTIONS, frozen before the run (the engine was written beside them and committed with them). P1 every instance's brute fate is abandoned on YES and served on NO, no open fate. P2 the margins print exactly 3/4 (YES: least cost with a over OPT, in units u) and 1/4 (NO, where the nearest subset sum is B + 1: least cost without a over OPT). KILL (printed): "fate mismatches: m of N", firing at m >= 1 or any open fate, over the corner family: every multiset of n <= 6 parts from 1..4, every B whose nearest subset sum from above is B (YES) or B + 1 (the tightest NO) with B - 1 a subset sum (a decoy; at B = 1 the empty sum), all of them, not drawn. CONTROL, read first: the engine on the two exhibited cells at T = 7/10, atom 1/10 with row (1, 0, 0): forced-abandoned at masses (11/20, 7/20, 1/10), rows (7/10, 3/10, 0), (1/2, 1/2, 0), one optimum (1, 2, 0) of cost 5/4; forced-served at (3/5, 3/10, 1/10), rows (1/2, 1/2, 0), (1/2, 2/5, 1/10), one optimum (2, 0, 1) of cost 13/10. The rational and the integer path agree on every family cell's OPT. Its break, read once in a scratch copy: an atom's cost doubled in the engine. FINDINGS. F0 CONTROLS. The engine reads both exhibited cells as frozen: OPT 5/4, one optimum (1, 2, 0), the atom forced-abandoned; OPT 13/10, one optimum (2, 0, 1), the atom forced-served. The rational and the integer path agree on OPT at 0 of 1926 cells off. The break (atom 0's cost doubled in fates(), a scratch copy) fails both control checks (OPT 9/5 and 11/5) and stops the run. F1 KILL MISSED, P1 HELD: 1926 instances (1644 YES, 282 NO), fate mismatches 0 of 1926, open fates 0, a counted check. F2 P2 HELD: the margins print exactly 3/4 at every YES and 1/4 at every NO, the derivation's, a counted check. TIERS. The hardness is a theorem (the derivation above, a reduction); F1 and F2 check its construction over the corner family. RUN RECORD. 5/5, 38.6 s, peak commit 7.9 MB under a memory guard (512 MB); the break read once, in a scratch copy. """ import os os.environ.setdefault("OPENBLAS_NUM_THREADS", "1") import sys import time from fractions import Fraction as F from itertools import combinations, combinations_with_replacement, product HERE = os.path.dirname(os.path.abspath(__file__)) sys.path.insert(0, HERE) from module_law import check, section, CHECKS # noqa: E402 def fates(w, rows, T): """Every rule enumerated: (OPT, optima, fate per atom: A, S or O).""" pre = [[sum(sorted(r, reverse=True)[:s]) for s in range(len(r) + 1)] for r in rows] best, optima = None, [] for rule in product(*[range(len(r) + 1) for r in rows]): cov = sum(wi * pre[i][s] for i, (wi, s) in enumerate(zip(w, rule))) if cov < T: continue cost = sum(wi * s for wi, s in zip(w, rule)) if best is None or cost < best: best, optima = cost, [rule] elif cost == best: optima.append(rule) fate = [] for i in range(len(w)): zero = [o[i] == 0 for o in optima] fate.append("A" if all(zero) else "S" if not any(zero) else "O") return best, optima, fate def least_with(w, rows, T, i, served): """The least cost over rules that serve atom i (served) or not.""" pre = [[sum(sorted(r, reverse=True)[:s]) for s in range(len(r) + 1)] for r in rows] best = None for rule in product(*[range(len(r) + 1) for r in rows]): if (rule[i] > 0) != served: continue cov = sum(wi * pre[j][s] for j, (wi, s) in enumerate(zip(w, rule))) if cov < T: continue cost = sum(wi * s for wi, s in zip(w, rule)) if best is None or cost < best: best = cost return best def reduction(b, B, scaled): """The cell of the derivation; atom a last. scaled: masses in units u/4, integers, with T in the same units.""" W = F(4 * B + 3, 4) p = (B + F(1, 2)) / W if scaled: w = [4 * x for x in b] + [4 * B + 3] rows = [(1, 0)] * len(b) + [(p, 1 - p)] return w, rows, 4 * B, F(1, 4) # one integer unit is u/4 u = 1 / (sum(b) + W) w = [x * u for x in b] + [W * u] rows = [(F(1), F(0))] * len(b) + [(p, 1 - p)] return w, rows, B * u, u def sums(b): return {sum(c) for n in range(len(b) + 1) for c in combinations(b, n)} def family(): out = [] for n in range(1, 7): for b in combinations_with_replacement(range(1, 5), n): S = sums(b) for B in range(1, sum(b) + 1): if B - 1 not in S: continue if B in S: out.append((b, B, True)) elif B + 1 in S: out.append((b, B, False)) return out def section_control(): section("A THE CONTROL: THE TWO EXHIBITED CELLS") T = F(7, 10) w1 = [F(11, 20), F(7, 20), F(1, 10)] r1 = [(F(7, 10), F(3, 10), F(0)), (F(1, 2), F(1, 2), F(0)), (F(1), F(0), F(0))] o1 = fates(w1, r1, T) check("control: the first cell abandons the atom, one optimum " "(1, 2, 0) of cost 5/4", o1[2][2] == "A" and o1[1] == [(1, 2, 0)] and o1[0] == F(5, 4), "OPT %s, optima %s, fates %s" % (o1[0], o1[1], o1[2])) w2 = [F(3, 5), F(3, 10), F(1, 10)] r2 = [(F(1, 2), F(1, 2), F(0)), (F(1, 2), F(2, 5), F(1, 10)), (F(1), F(0), F(0))] o2 = fates(w2, r2, T) check("control: the second cell serves the atom, one optimum " "(2, 0, 1) of cost 13/10", o2[2][2] == "S" and o2[1] == [(2, 0, 1)] and o2[0] == F(13, 10), "OPT %s, optima %s, fates %s" % (o2[0], o2[1], o2[2])) def section_family(): section("B THE CORNER FAMILY") fam = family() t0 = time.time() bad = opens = paths = 0 yes = no = 0 m_yes, m_no = set(), set() for b, B, ans in fam: w, rows, T, _ = reduction(b, B, scaled=True) opt, _, fate = fates(w, rows, T) wq, rq, Tq, u = reduction(b, B, scaled=False) optq = fates(wq, rq, Tq)[0] paths += optq / u != F(opt, 4) a = fate[-1] opens += a == "O" bad += a != ("A" if ans else "S") i = len(b) if ans: yes += 1 m_yes.add(F(least_with(w, rows, T, i, True) - opt, 4)) else: no += 1 m_no.add(F(least_with(w, rows, T, i, False) - opt, 4)) n = len(fam) print(" %d instances (%d YES, %d NO), n <= 6, parts 1..4 [%.0f s]" % (n, yes, no, time.time() - t0)) check("control: the rational and the integer path agree on OPT", paths == 0, "%d of %d off" % (paths, n)) print(" fate mismatches: %d of %d; open fates: %d" % (bad, n, opens)) print(" margins, units u: YES %s; NO %s" % (sorted(str(x) for x in m_yes), sorted(str(x) for x in m_no))) check("every fate is the answer: abandoned on YES, served on NO", bad == 0 and opens == 0, "%d mismatches, %d open, of %d" % (bad, opens, n)) check("the margins are exactly 3/4 (YES) and 1/4 (NO)", m_yes == {F(3, 4)} and m_no == {F(1, 4)}, "YES %s, NO %s" % (sorted(map(str, m_yes)), sorted(map(str, m_no)))) print(" P1 fate is the answer, no open fate: %s" % ("HELD" if bad == 0 and opens == 0 else "MISSED")) print(" P2 margins 3/4 and 1/4 exactly: %s" % ("HELD" if m_yes == {F(3, 4)} and m_no == {F(1, 4)} else "MISSED")) print(" KILL (a mismatch or an open fate): %s" % ("FIRED" if bad or opens else "MISSED")) def main(): t0 = time.time() section_control() if not all(CHECKS): print("CONTROL FAILED: nothing below is read.") raise SystemExit(1) section_family() print("\n%d/%d checks PASS, %.1f s" % (sum(CHECKS), len(CHECKS), time.time() - t0)) raise SystemExit(0 if all(CHECKS) else 1) if __name__ == "__main__": main()