İçindekiler: :: Library Catalog

Kaydedildi:

Detaylı Bibliyografya
Yazar:	Rao, Huiying
Materyal Türü:	Recurso digital
Dil:	İngilizce
Baskı/Yayın Bilgisi:	Zenodo 2026
Konular:	CDCL SAT collapse chain unit propagation clause learning phase transition uncertainty reduction information monotonicity hard wall NP-hard
Online Erişim:	https://doi.org/10.5281/zenodo.19600733
Etiketler:	Etiketle Etiket eklenmemiş, İlk siz ekleyin!

İçindekiler:

We prove that the Conflict-Driven Clause Learning (CDCL) algorithm is formally equivalent to a branching collapse chain: a collection of collapse chains that share information through learned clauses, with globally monotone non-decreasing information content despite local backtracking. The equivalence resolves the backtracking paradox: backtracking does not reverse collapse. It terminates the current chain and initiates a new one from a checkpoint, with the learned clause serving as the irreversible information transfer between chains. The global information content of CDCL is monotone non-decreasing (Information Monotonicity Theorem), consistent with the branching collapse chain definition. Three consequences follow: (1) The Information Monotonicity Theorem — each k-literal learned clause contributes n−k bits of information, explaining why modern CDCL implementations prioritise short clauses; (2) The Gradient Impossibility Theorem — no differentiable collapse operator can improve upon CDCL for SAT near the phase transition, providing a principled explanation for the hard wall; (3) Empirical validation — 47 out of 100 variables exhibit intrinsic uncertainty across satisfying assignments at α=4.2, confirming that residual uncertainty after CDCL is structural, not epistemic. Part of the NSD / MOEH research programme. Companion papers: "Collapse as a Unifying Language for NP-Hard Optimisation" (Zenodo: 10.5281/zenodo.19574013) and "A Landscape-Aware Classification Framework for NP-Hard Optimisation Problems" (under review at JAIR #22499).

Benzer Materyaller