A randomized algorithm for 3-SAT

DOI10.1007/s11786-010-0036-3zbMath1205.68177arXiv0906.1849MaRDI QIDQ626900

Subhas Kumar Ghosh, Janardan Misra

Publication date: 19 February 2011

Published in: Mathematics in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0906.1849

zbMATH Keywords

analysis of algorithms; randomized algorithm; Boolean satisfiability; exponential time algorithm

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W20: Randomized algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An improved deterministic local search algorithm for 3-SAT
• Randomized algorithms for 3-SAT
• Solving satisfiability in less than \(2^ n\) steps
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• A probabilistic algorithm for \(k\)-SAT based on limited local search and restart
• A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
• New methods for 3-SAT decision and worst-case analysis
• The complexity of Unique \(k\)-SAT: An isolation lemma for \(k\)-CNFs
• An improved exponential-time algorithm for k -SAT
• A necessary condition on minimal cube numberings
• A machine program for theorem-proving
• The complexity of theorem-proving procedures
• Theory and Applications of Satisfiability Testing