1"""Stage 5: heuristic attacks on Theorem 5.1 and on the boundary certificates.23Attack A (theorem): simulated annealing over 11-subsets S of V(P(n,5)),4maximising |cl(S)|, for 23 <= n <= 60 and a sample of larger n. Any S with5cl(S) = V would be a counterexample to Z(P(n,5)) = 12. Positive controls:6(n, s) = (22, 11), (21, 10), (13, 9), (11, 6), where forcing sets exist.78Attack B (certificates): simulated annealing over 18-subsets X, minimising9|dX|, for 26 <= n <= 60 and a sample up to n = 200. Any X with |dX| <= 1110would contradict the DRAT-certified unsatisfiability of F(n,18) (n <= 154)11or Lemma 3.2 (n > 154). Positive controls: n = 22, 23, 25 (beta_18 = 10,1211, 10 in results/tables/boundary_table.csv) and p = 20 at n = 24 (11).1314Everything here is written from scratch (bitmask closure, no project15imports). Seeds are fixed and recorded. Output:16results/robustness/local_search_attacks.json17"""18import json19import math20import os21import random22import sys23import time2425ROOT = os.path.dirname(os.path.dirname(os.path.dirname(os.path.abspath(__file__))))26os.chdir(ROOT)272829def masks(n, k):30 N = 2 * n31 nb = [0] * N32 for i in range(n):33 u, v = i, n + i34 for t in ((i + 1) % n, (i - 1) % n, v):35 nb[u] |= 1 << t36 for t in (n + (i + k) % n, n + (i - k) % n, u):37 nb[v] |= 1 << t38 return N, nb394041def closure_size(N, nb, S):42 B = S43 full = (1 << N) - 144 changed = True45 while changed and B != full:46 changed = False47 rest = B48 while rest:49 low = rest & -rest50 b = low.bit_length() - 151 rest ^= low52 white = nb[b] & ~B53 if white and white & (white - 1) == 0:54 B |= white55 changed = True56 return bin(B).count("1")575859def boundary_size(nb, X):60 NX = 061 rest = X62 while rest:63 low = rest & -rest64 NX |= nb[low.bit_length() - 1]65 rest ^= low66 return bin(NX & ~X).count("1")676869def anneal(N, score, s, iters, restarts, rng, target, maximise=True):70 """Generic swap-move annealing over s-subsets of range(N). Returns best score and set."""71 best_val, best_set = None, None72 sign = 1 if maximise else -173 for _ in range(restarts):74 cur = rng.sample(range(N), s)75 curmask = sum(1 << w for w in cur)76 cur_val = score(curmask)77 if best_val is None or sign * cur_val > sign * best_val:78 best_val, best_set = cur_val, curmask79 T0, T1 = 1.5, 0.0580 for it in range(iters):81 T = T0 * (T1 / T0) ** (it / max(1, iters - 1))82 i = rng.randrange(s)83 w_out = cur[i]84 while True:85 w_in = rng.randrange(N)86 if not (curmask >> w_in) & 1:87 break88 newmask = (curmask & ~(1 << w_out)) | (1 << w_in)89 val = score(newmask)90 d = sign * (val - cur_val)91 if d >= 0 or rng.random() < math.exp(d / T):92 cur[i] = w_in93 curmask, cur_val = newmask, val94 if sign * val > sign * best_val:95 best_val, best_set = val, newmask96 if (maximise and val >= target) or (not maximise and val <= target):97 return best_val, best_set98 return best_val, best_set99100101def mask_to_labels(n, m):102 return ["%s%d" % ("u" if w < n else "v", w if w < n else w - n) for w in range(2 * n) if (m >> w) & 1]103104105def main():106 seed = 20261030107 rng = random.Random(seed)108 out = {"seed": seed, "attack_A": [], "attack_A_controls": [], "attack_B": [], "attack_B_controls": []}109 t0 = time.time()110 # ---- Attack A controls111 for (n, s) in [(11, 6), (13, 9), (21, 10), (22, 11)]:112 N, nb = masks(n, 5)113 val, S = anneal(N, lambda m: closure_size(N, nb, m), s, 20000, 6, rng, N, True)114 out["attack_A_controls"].append({"n": n, "s": s, "best_closure": val, "N": N, "forcing_found": val == N,115 "S": mask_to_labels(n, S) if val == N else None})116 # ---- Attack A: 11-sets for n = 23..60 and sample117 ns = list(range(23, 61)) + [70, 80, 96, 120, 154, 155, 200]118 for n in ns:119 N, nb = masks(n, 5)120 val, S = anneal(N, lambda m: closure_size(N, nb, m), 11, 15000, 4, rng, N, True)121 rec = {"n": n, "s": 11, "best_closure": val, "N": N, "forcing_found": val == N}122 if val == N:123 rec["COUNTEREXAMPLE_S"] = mask_to_labels(n, S)124 out["attack_A"].append(rec)125 tA = time.time() - t0126 # ---- Attack B controls127 for (n, p, expect) in [(22, 18, 10), (23, 18, 11), (25, 18, 10), (24, 20, 11), (24, 18, 12)]:128 N, nb = masks(n, 5)129 val, X = anneal(N, lambda m: boundary_size(nb, m), p, 40000, 6, rng, expect, False)130 out["attack_B_controls"].append({"n": n, "p": p, "expected_beta_from_table": expect, "best_boundary": val,131 "X": mask_to_labels(n, X)})132 # ---- Attack B: 18-sets, n = 26..60 and sample133 ns = list(range(26, 61)) + [70, 80, 96, 120, 154, 155, 160, 200]134 for n in ns:135 N, nb = masks(n, 5)136 val, X = anneal(N, lambda m: boundary_size(nb, m), 18, 40000, 5, rng, 11, False)137 rec = {"n": n, "p": 18, "best_boundary": val, "violation": val <= 11}138 if val <= 11:139 rec["COUNTEREXAMPLE_X"] = mask_to_labels(n, X)140 out["attack_B"].append(rec)141 out["wall_seconds_A"] = round(tA, 1)142 out["wall_seconds_total"] = round(time.time() - t0, 1)143 out["attack_A_any_counterexample"] = any(r["forcing_found"] for r in out["attack_A"])144 out["attack_B_any_violation"] = any(r["violation"] for r in out["attack_B"])145 out["attack_A_controls_all_found"] = all(r["forcing_found"] for r in out["attack_A_controls"])146 out["attack_B_controls_reached_table_value"] = all(r["best_boundary"] == r["expected_beta_from_table"] for r in out["attack_B_controls"])147 json.dump(out, open("results/robustness/local_search_attacks.json", "w"), indent=1)148 print("A controls found:", out["attack_A_controls_all_found"], [(r["n"], r["best_closure"], r["N"]) for r in out["attack_A_controls"]])149 print("A counterexample:", out["attack_A_any_counterexample"], "best closures:", [(r["n"], r["best_closure"], r["N"]) for r in out["attack_A"]])150 print("B controls:", [(r["n"], r["p"], r["best_boundary"], r["expected_beta_from_table"]) for r in out["attack_B_controls"]])151 print("B violation:", out["attack_B_any_violation"], "best boundaries:", [(r["n"], r["best_boundary"]) for r in out["attack_B"]])152 print("wall", out["wall_seconds_total"])153154155if __name__ == "__main__":156 main()157