Improved polynomial algorithm for 3-SAT

MaRDI QIDQ2888310zbMATH OpenFDO

Authors Narendra S. Chaudhari

Publication date 30 May 2012

Published in The Journal of the Indian Academy of Mathematics (Search for Journal in Brave)

zbMATH Keywords

3-SATconditionalliteralpolynomial solvability

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 515744
• An improved deterministic local search algorithm for 3-SAT
• Theory and Applications of Satisfiability Testing
• scientific article; zbMATH DE number 2086385
• An efficient algorithm for the 3-satisfiability problem

Cited in

(3)

• A polynomial-time reduction from the 3SAT problem to the generalized string puzzle problem
• An efficient algorithm for 3NF determination
• An improvement of the algorithm of Hertli for the unique 3SAT problem

This page was built for publication: Improved polynomial algorithm for 3-SAT

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