Exact satisfiability of linear CNF formulas

DOI10.1016/j.dam.2018.05.018zbMath1403.68084OpenAlexW2807072029MaRDI QIDQ1627839

Bernd R. Schuh

Publication date: 3 December 2018

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2018.05.018

zbMATH Keywords

complexityNP-completenessXSAT\(k\)-uniformity\(l\)-regularityexact linear formula

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• XSAT and NAE-SAT of linear CNF classes
• A Note on a Combinatorial Problem