Computational complexity of some restricted instances of 3-SAT

DOI10.1016/J.DAM.2006.07.009MaRDI QIDQ875598zbMATH OpenOpenAlexFDO

Authors Piotr Berman, Marek Karpinski, Alex Scott

Publication date 13 April 2007

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

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

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• On simplified NP-complete variants of \textsc{Monotone 3-Sat}
• One More Occurrence of Variables Makes Satisfiability Jump from Trivial to NP-Complete
• On the parameterized complexity of \((k,s)\)-SAT
• Uniquely satisfiable k-SAT instances with almost minimal occurrences of each variable
• The Monotone Satisfiability Problem with Bounded Variable Appearances

Cites work

• (2+\(f\)(\(n\)))-SAT and its properties.
• A simplified NP-complete satisfiability problem
• Determining computational complexity from characteristic ``phase transitions
• scientific article; zbMATH DE number 1113997 (Why is no real title available?)
• On the r,s-SAT satisfiability problem and a conjecture of Tovey
• One More Occurrence of Variables Makes Satisfiability Jump from Trivial to NP-Complete
• The complexity of theorem-proving procedures
• Tricritical points in random combinatorics: the -SAT case

Cited in

(22)

• Using clausal graphs to determine the computational complexity of \(k\)-bounded positive one-in-three SAT
• On the parameterized complexity of \((k,s)\)-SAT
• A polynomial-time reduction from the 3SAT problem to the generalized string puzzle problem
• On simplified NP-complete variants of \textsc{Monotone 3-Sat}
• On a simple hard variant of \textsc{Not-All-Equal} 3-\textsc{Sat}
• On inverse chromatic number problems (extended abstract)
• Computationally hard problems: 3-SAT and its polynomial solvability
• MRHS Equation Systems that can be Solved in Polynomial Time
• On the hardness of satisfiability with bounded occurrences in the polynomial-time hierarchy
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• On the Complexity of Hmelevskii’s Theorem and Satisfiability of Three Unknown Equations
• scientific article; zbMATH DE number 1113997 (Why is no real title available?)
• On minimum reload cost cycle cover
• Hard satisfiable 3-SAT instances via autocorrelation
• Planar 3-SAT with a clause/variable cycle
• Conditional hardness for satisfiable 3-CSPs
• (2/2/3)-SAT problem and its applications in dominating set problems
• Three‐query PCPs with perfect completeness over non‐Boolean domains
• Mathematical Foundations of Computer Science 2003
• Point-to-point and milk run delivery scheduling: models, complexity results, and algorithms based on Benders decomposition
• Computing bond orders in molecule graphs
• A tractability gap beyond nim-sums: it's hard to tell whether a bunch of superstars are losers

This page was built for publication: Computational complexity of some restricted instances of 3-SAT

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