Linear CNF formulas and satisfiability

DOI10.1016/j.dam.2008.03.031zbMath1186.68223MaRDI QIDQ1028433

Stefan Porschen, Ewald Speckenmeyer, Zhao, Xishun

Publication date: 30 June 2009

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

Full work available at URL: http://e-archive.informatik.uni-koeln.de/520/2/zaik2006-520.pdf

zbMATH Keywords

NP-completeness; Latin square; resolution; satisfiability; finite projective plane; linear CNF formula

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C65: Hypergraphs

Related Items

A general method for forbidden induced subgraph sandwich problem NP-completeness, Resolution and linear CNF formulas: improved \((n,3)\)-\textsc{MaxSAT} algorithms, XSAT and NAE-SAT of linear CNF classes, Improved MaxSAT Algorithms for Instances of Degree 3, On Some SAT-Variants over Linear Formulas, On Some Aspects of Mixed Horn Formulas, The Lovász Local Lemma and Satisfiability

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A short proof of Fisher's inequality
• A simplified NP-complete satisfiability problem
• Topics on Steiner systems. Ed. by C. C. Lindner and A. Rosa
• A fast parallel SAT-solver -- efficient workload balancing
• A perspective on certain polynomial-time solvable classes of satisfiability
• An extension of a theorem of the Bruijn and Erdős on combinatorial designs
• An existence theory for pairwise balanced designs. II: Structure of PBD- closed sets and the existence conjectures
• A CNF Class Generalizing Exact Linear Formulas
• On Representatives of Subsets
• Determining computational complexity from characteristic ‘phase transitions’