XSAT and NAE-SAT of linear CNF classes

DOI10.1016/j.dam.2013.10.030zbMath1284.05106OpenAlexW1968692677MaRDI QIDQ2440094

Tatjana Schmidt, Stefan Porschen, Ewald Speckenmeyer, Andreas Wotzlaw

Publication date: 27 March 2014

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

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

zbMATH Keywords

linear hypergraphcounting problemfinite projective planeexact satisfiabilitylinear formulabicolorabilitynot-all-equal satisfiability

Mathematics Subject Classification ID

Hypergraphs (05C65) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Exact satisfiability of linear CNF formulas, Constrained stable marriage with free edges or few blocking pairs, Placing quantified variants of 3-SAT and \textsc{not-all-equal} 3-SAT in the polynomial hierarchy, On the hardness of deciding the equality of the induced and the uniquely restricted matching number, On the complexity of packing rainbow spanning trees, Unnamed Item, Exploring the complexity of the integer image problem in the \(\max\)-algebra, On the complexity of finding large odd induced subgraphs and odd colorings, NAE-resolution: A new resolution refutation technique to prove not-all-equal unsatisfiability, On a simple hard variant of \textsc{Not-All-Equal} 3-\textsc{Sat}, The stable marriage problem with ties and restricted edges, Complexity of shift bribery for iterative voting rules

Uses Software

• satUZK

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A short proof of Fisher's inequality
• Linear CNF formulas and satisfiability
• Axioms and hulls
• A fast parallel SAT-solver -- efficient workload balancing
• New algorithms for exact satisfiability
• The Non-Existence of Finite Projective Planes of Order 10
• On the Complexity of General Graph Factor Problems
• Unsatisfiable Linear CNF Formulas Are Large and Complex.
• A Note on Unsatisfiable k-CNF Formulas with Few Occurrences per Variable
• On Some SAT-Variants over Linear Formulas
• Algorithms for Variable-Weighted 2-SAT and Dual Problems
• One More Occurrence of Variables Makes Satisfiability Jump from Trivial to NP-Complete
• Complexity Results for Linear XSAT-Problems
• Theory and Applications of Satisfiability Testing
• The complexity of satisfiability problems
• Color critical hypergraphs with many edges
• Approximation algorithms and hardness results for the clique packing problem