2026-07-22T06:37:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16683 2024-03-06T10:58:02Z ddc:004 open_access

A Generalization of the Satisfiability Coding Lemma and Its Applications Mossé, Milan Sha, Harry Tan, Li-Yang Prime Implicants Satisfiability Coding Lemma Blake Canonical Form k-SAT The seminal Satisfiability Coding Lemma of Paturi, Pudlák, and Zane is a coding scheme for satisfying assignments of k-CNF formulas. We generalize it to give a coding scheme for implicants and use this generalized scheme to establish new structural and algorithmic properties of prime implicants of k-CNF formulas. Our first application is a near-optimal bound of n⋅ 3^{n(1-Ω(1/k))} on the number of prime implicants of any n-variable k-CNF formula. This resolves an open problem from the Ph.D. thesis of Talebanfard, who proved such a bound for the special case of constant-read k-CNF formulas. Our proof is algorithmic in nature, yielding an algorithm for computing the set of all prime implicants - the Blake Canonical Form - of a given k-CNF formula. The problem of computing the Blake Canonical Form of a given function is a classic one, dating back to Quine, and our work gives the first non-trivial algorithm for k-CNF formulas. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Milan Mossé and Harry Sha and Li-Yang Tan 2022 Is Part Of LIPIcs, Volume 236, 25th International Conference on Theory and Applications of Satisfiability Testing (SAT 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SAT.2022.9 urn:nbn:de:0030-drops-166837 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAT.2022.9 eng https://creativecommons.org/licenses/by/4.0/legalcode