Exact 3-satisfiability is decidable in time \(O(2^{0.16254 n})\)

DOI10.1007/s10472-005-0428-2zbMath1099.68042OpenAlexW2474390896MaRDI QIDQ1777401

Stefan Porschen, Ewald Speckenmeyer, Bert Randerath

Publication date: 13 May 2005

Published in: Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10472-005-0428-2

zbMATH Keywords

NP-completenessperfect matchingexact satisfiabilityautonomous clause patternformula graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Classical propositional logic (03B05)

Related Items (4)

Partition into triangles on bounded degree graphs ⋮ On variable-weighted exact satisfiability problems ⋮ New algorithms for exact satisfiability ⋮ Faster than classical quantum algorithm for dense formulas of exact satisfiability and occupation problems

Cites Work

• Matching theory
• The complexity of satisfiability problems
• Unnamed Item
• Unnamed Item

This page was built for publication: Exact 3-satisfiability is decidable in time \(O(2^{0.16254 n})\)