XSAT and NAE-SAT of linear CNF classes

DOI10.1016/j.dam.2013.10.030zbMath1284.05106MaRDI 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 hypergraph; counting problem; finite projective plane; exact satisfiability; linear formula; bicolorability; not-all-equal satisfiability

Mathematics Subject Classification ID

05C65: Hypergraphs

05C15: Coloring of graphs and hypergraphs

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

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

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