Computational complexity of some restricted instances of 3-SAT

DOI10.1016/J.DAM.2006.07.009zbMath1111.68044OpenAlexW2038784300MaRDI QIDQ875598

Piotr Berman, Marek Karpinski, Alexander D. 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

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

Related Items (7)

Point-to-point and milk run delivery scheduling: models, complexity results, and algorithms based on Benders decomposition ⋮ Computing bond orders in molecule graphs ⋮ MRHS Equation Systems that can be Solved in Polynomial Time ⋮ On the parameterized complexity of \((k,s)\)-SAT ⋮ On minimum reload cost cycle cover ⋮ Unnamed Item ⋮ Using clausal graphs to determine the computational complexity of \(k\)-bounded positive one-in-three SAT

Cites Work

• Unnamed Item
• A simplified NP-complete satisfiability problem
• (2+\(f\)(\(n\)))-SAT and its properties.
• 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
• Tricritical points in random combinatorics: the -SAT case
• Determining computational complexity from characteristic ‘phase transitions’
• The complexity of theorem-proving procedures

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