Complexity Results for Linear XSAT-Problems

DOI10.1007/978-3-642-14186-7_21MaRDI QIDQ4930593zbMATH OpenOpenAlexFDO

Authors Stefan Porschen, Tatjana Schmidt, Ewald Speckenmeyer

Publication date 29 September 2010

Published in Theory and Applications of Satisfiability Testing – SAT 2010 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-14186-7_21

zbMATH Keywords

exact satisfiabilityfinite projective planelinear formulaNP-completenessregularity

Mathematics Subject Classification ID

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

Recommendations

• XSAT and NAE-SAT of linear CNF classes
• scientific article; zbMATH DE number 1351079
• Publication:4886070
• On satisfiability problems with a linear structure
• Exponential complexity of satisfiability testing for linear-size Boolean formulas
• Theory and Applications of Satisfiability Testing
• Parameterized complexity of constraint satisfaction problems
• scientific article; zbMATH DE number 3849198
• The complexity of satisfiability problems
• STACS 2004

Cited in

(4)

• Exact satisfiability of linear CNF formulas
• Exact satisfiabitity with jokers
• XSAT and NAE-SAT of linear CNF classes
• On Some SAT-Variants over Linear Formulas

This page was built for publication: Complexity Results for Linear XSAT-Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4930593)