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

DOI10.1016/J.TCS.2020.02.010MaRDI QIDQ2310754zbMATH OpenOpenAlexFDO

Authors Andreas Darmann, Janosch Döcker

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

bounded variable appearancescomputational complexitylinear formulasnot-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)

Recommendations

• On simplified NP-complete variants of \textsc{Monotone 3-Sat}
• A preliminary investigation of satisfiability problems not harder than 1-in-3-SAT
• On strongly planar not-all-equal 3SAT
• Placing quantified variants of 3-SAT and \textsc{not-all-equal} 3-SAT in the polynomial hierarchy
• Computational complexity of some restricted instances of 3-SAT
• New upper bound for the \#3-SAT problem
• Hard random 3-SAT problems and the Davis-Putnam procedure
• Conditional hardness for satisfiable 3-CSPs
• Hard satisfiable 3-SAT instances via autocorrelation
• Computationally hard problems: 3-SAT and its polynomial solvability

Cites work

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

Cited in

(19)

• Partitioning \(H\)-free graphs of bounded diameter
• Placing quantified variants of 3-SAT and \textsc{not-all-equal} 3-SAT in the polynomial hierarchy
• On simplified NP-complete variants of \textsc{Monotone 3-Sat}
• On strongly planar not-all-equal 3SAT
• Parameterized Complexity of Conflict-Free Graph Coloring
• Hard satisfiable 3-SAT instances via autocorrelation
• On locally-balanced 2-partitions of bipartite graphs
• Conditional hardness for satisfiable 3-CSPs
• Theory and Applications of Satisfiability Testing
• Cutting Barnette graphs perfectly is hard
• Finding maximum common contractions between phylogenetic networks
• On the parameterized complexity of computing good edge-labelings
• Graceful coloring is computationally hard
• Defensive alliances in signed networks
• Inapproximability of counting hypergraph colourings
• Highly irregular graph decompositions
• On connections between k-coloring and Euclidean k-means
• Mim-width is paraNP-complete
• Exact algorithms and hardness result for the Boolean connectivity problem of k-Horn formulas

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

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