XSAT and NAE-SAT of linear CNF classes
From MaRDI portal
Publication:2440094
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
linear hypergraph; counting problem; finite projective plane; exact satisfiability; linear formula; bicolorability; not-all-equal satisfiability
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
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