Metraipolis › archive › dc_3fa314396f82

Subsumption-Free Private-Pivot Learning in Resolvable Network-Based SAT Solving — arXiv:2609.34880

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.34880
License (as archived)
CC0-1.0
Archived
2026-10-08T00:42:59.436Z
SHA-256 of the archived text
c3d141e1077d1a14834485974a173f33ced66fd400e827b89ac86d74f35f1928
Stable URL of this page
https://metraipolis.com/documento/dc_3fa314396f82

How to cite

Subsumption-Free Private-Pivot Learning in Resolvable Network-Based SAT Solving — arXiv:2609.34880 — arXiv (en), https://arxiv.org/abs/2609.34880 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_3fa314396f82 (Metraipolis archive dc_3fa314396f82, sha256 c3d141e1077d1a14834485974a173f33ced66fd400e827b89ac86d74f35f1928)
BibTeX
@misc{dc3fa314396f82,
  title = {Subsumption-Free Private-Pivot Learning in Resolvable Network-Based SAT Solving — arXiv:2609.34880},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.34880},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_3fa314396f82; sha256 c3d141e1077d1a14834485974a173f33ced66fd400e827b89ac86d74f35f1928},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.34880. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

A resolvable network is a directed-graph representation of SAT: every SAT instance can be translated into an RN, and every RN has an associated CNF formula. Each reach represents one clause. In a mixed reach, the head and tail are disjoint sets of variables containing the variables occurring negatively and positively in the clause, respectively; the distinguished symbols Source and Sink represent a missing negative- or positive-literal side. RN-Solver is a proof-of-concept SAT solver based on this representation. Its all-positive clauses are represented by white reaches, and its token distributions are the inclusion-minimal hitting sets of the current white tails, generated by monotone CNF-DNF dualization. RN-Solver learns new white reaches by private-pivot resolution, a structured resolution sequence that uses old white reaches as pivot witnesses. In the original algorithm, every candidate white reach generated by such a chain was followed by a global subsumption test against the current network. Profiling showed that this subsumption test can dominate the runtime on random 3-SAT instances. We show that this check is unnecessary when the mixed reach used for learning is falsified by the current token distribution, meaning that the distribution makes all variables in the head true and all variables in the tail false. The key invariant is simple: the resulting white tail is disjoint from the triggering token distribution, while the same distribution intersects every old white tail. Hence no old white reach can subsume the generated reach. This structural observation allows us to construct a simpler, snapshot-based, subsumption-free variant of RN-Solver, where each main-loop iteration uses a fixed set of old reaches and installs newly generated white reaches only at the end of the iteration. We prove soundness of the revised algorithm. Empirical evaluation confirms the elimination of the targeted checks: within an 8 second budget, snapshot/full-DNF solves 963 of 1,000 uf20-91 instances, compared with 724 for the original control flow. A separate 100-instance comparison identifies exact incremental DNF as the most effective of the three tested configurations.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-29 in cs.LO).
Categorie arXiv: Logic in Computer Science (cs.LO).
Pagina del lavoro: https://arxiv.org/abs/2609.34880 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-08T00:17:09.495Z dalla pagina https://arxiv.org/catchup/cs.LO/2026-09-29?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).