On a simple hard variant of \textsc{Not-All-Equal} 3-\textsc{Sat}

DOI10.1016/j.tcs.2020.02.010zbMath1433.68272OpenAlexW3005839441MaRDI QIDQ2310754

Janosch Döcker, Andreas Darmann

Publication date: 6 April 2020

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2020.02.010

zbMATH Keywords

computational complexitylinear formulasbounded variable appearancesnot-all-equal 3-satisfiability

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computational aspects of satisfiability (68R07)

Related Items (4)

Partitioning \(H\)-free graphs of bounded diameter ⋮ ON LOCALLY-BALANCED 2-PARTITIONS OF BIPARTITE GRAPHS ⋮ On simplified NP-complete variants of \textsc{Monotone} 3\textsc{-Sat} ⋮ Parameterized Complexity of Conflict-Free Graph Coloring

Cites Work

• On the complexity of deciding whether the regular number is at most two
• On vertex coloring without monochromatic triangles
• XSAT and NAE-SAT of linear CNF classes
• The complexity of satisfiability problems

This page was built for publication: On a simple hard variant of \textsc{Not-All-Equal} 3-\textsc{Sat}