fatehard.py
Checks: SETS: Deciding a fate encodes subset sum theorem.
Cited on: SETS.
To run it: save fatehard.py, with module_law.py beside it; standard library only.
"""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()