On simplified NP-complete variants of \textsc{Monotone 3-Sat}

DOI10.1016/J.DAM.2020.12.010MaRDI QIDQ2223685zbMATH OpenOpenAlexFDO

Authors Andreas Darmann, Janosch Döcker

Publication date 1 February 2021

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

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

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Computational aspects of satisfiability (68R07)

Recommendations

• The Monotone Satisfiability Problem with Bounded Variable Appearances
• On a simple hard variant of \textsc{Not-All-Equal} 3-\textsc{Sat}
• Computational complexity of some restricted instances of 3-SAT
• A simplified NP-complete MAXSAT problem
• One More Occurrence of Variables Makes Satisfiability Jump from Trivial to NP-Complete

Cites work

• A simplified NP-complete satisfiability problem
• A special planar satisfiability problem and a consequence of its NP- completeness
• Complexity of automaton identification from given data
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• On a simple hard variant of \textsc{Not-All-Equal} 3-\textsc{Sat}
• On the parameterized complexity of \((k,s)\)-SAT
• Optimal binary space partitions for segments in the plane
• Planar 3-SAT with a clause/variable cycle
• Planar Formulae and Their Uses
• The complexity of theorem-proving procedures
• The Lovász Local Lemma and Satisfiability
• The Monotone Satisfiability Problem with Bounded Variable Appearances
• Theory and Applications of Satisfiability Testing
• Two-segmented channel routing is strong NP-complete

Cited in

(18)

• Using clausal graphs to determine the computational complexity of \(k\)-bounded positive one-in-three SAT
• Complexity results for two kinds of colored disconnections of graphs
• Placing quantified variants of 3-SAT and \textsc{not-all-equal} 3-SAT in the polynomial hierarchy
• Subexponential algorithms for variants of the homomorphism problem in string graphs
• On a simple hard variant of \textsc{Not-All-Equal} 3-\textsc{Sat}
• On the approximation hardness of geodetic set and its variants
• A simplified NP-complete MAXSAT problem
• Mathematical Foundations of Computer Science 2003
• Minimizing corners in colored rectilinear grids
• Polarised random k-SAT
• Small unsatisfiable k-CNFs with bounded literal occurrence
• Finding d-cuts in graphs of bounded diameter, graphs of bounded radius and H-free graphs
• Disjoint temporal walks under waiting time constraints
• Linear extensions of rotor-routing in directed graphs: reachability problems
• Parameterized spanning tree congestion
• Revisiting directed disjoint paths on tournaments (and relatives)
• Structural parameters for Steiner orientation
• Computational complexity of some restricted instances of 3-SAT

This page was built for publication: On simplified NP-complete variants of \textsc{Monotone 3-Sat}

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