Algorithms for Sat and upper bounds on their complexity

DOI10.1023/A:1025645221773MaRDI QIDQ2487388zbMATH OpenOpenAlexFDO

Authors Edward A. Hirsch, E. Ya. Dantsin, S. V. Ivanov, Maxim Vsemirnov

Publication date 5 August 2005

Published in Journal of Mathematical Sciences (New York) (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1023/a:1025645221773

zbMATH Keywords

propositional satisfiability problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• scientific article; zbMATH DE number 1222558
• Theory and Applications of Satisfiability Testing
• New worst-case upper bounds for SAT
• New worst-case upper bounds for SAT
• scientific article; zbMATH DE number 956858

Cited in

(18)

• Typical case complexity of satisfiability algorithms and the threshold phenomenon
• On complete one-way functions
• scientific article; zbMATH DE number 7310227 (Why is no real title available?)
• Better Algorithms for Satisfiability Problems for Formulas of Bounded Rank-width
• An enumerative algorithm for \#2SAT
• UnitWalk: A new SAT solver that uses local search guided by unit clause elimination
• Solving NP-Complete Problems with Quantum Search
• STACS 2004
• scientific article; zbMATH DE number 1555929 (Why is no real title available?)
• New worst-case upper bounds for SAT
• A \(2^{|E|/4}\)-time algorithm for MAX-CUT
• Min-wise independent groups
• An initial study of time complexity in infinite-domain constraint satisfaction
• scientific article; zbMATH DE number 1182571 (Why is no real title available?)
• Complexity of SAT Problems, Clone Theory and the Exponential Time Hypothesis
• About some UP-based polynomial fragments of SAT
• Hard satisfiable instances for DPLL-type algorithms
• Algorithms for four variants of the exact satisfiability problem

This page was built for publication: Algorithms for Sat and upper bounds on their complexity

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