scientific article; zbMATH DE number 4039349

MaRDI QIDQ3777498zbMATH OpenFDO

Authors E. Ya. Dantsin

Publication date 1987

zbMATH Keywords

effectivenessNP-completenesssatisfiability problem

Mathematics Subject Classification ID

Mechanization of proofs and logical operations (03B35) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• The complexity of satisfiability problems
• Solving satisfiability in less than \(2^ n\) steps
• scientific article; zbMATH DE number 1222558
• An algorithm for the satisfiability problem of formulas in conjunctive normal form
• A complexity analysis of the SAT problem

Cited in

(31)

• Nonserial dynamic programming formulations of satisfiability
• On the greedy algorithm for satisfiability
• Measure of formulas: Calculation and a polynomial class for satisfiability
• Some interesting research directions in satisfiability
• Running time experiments on some algorithms for solving propositional satisfiability problems
• Special issues on The satisfiability problem (pp. 1--244) including papers from the 1st workshop on satisfiability, Certosa di Pontignano, Italy, April 29--May 3, 1996 and Boolean functions (pp. 245--479)
• Separating signs in the propositional satisfiability problem
• Typical case complexity of satisfiability algorithms and the threshold phenomenon
• Algorithms for Solving Satisfiability Problems with Qualitative Preferences
• scientific article; zbMATH DE number 2177624 (Why is no real title available?)
• scientific article; zbMATH DE number 991069 (Why is no real title available?)
• On the weights of Boolean functions representable by 2-CNF or 3-CNF
• scientific article; zbMATH DE number 6528599 (Why is no real title available?)
• scientific article; zbMATH DE number 4023248 (Why is no real title available?)
• scientific article; zbMATH DE number 1222558 (Why is no real title available?)
• scientific article; zbMATH DE number 1113992 (Why is no real title available?)
• scientific article; zbMATH DE number 1182571 (Why is no real title available?)
• scientific article; zbMATH DE number 1943080 (Why is no real title available?)
• scientific article; zbMATH DE number 6874827 (Why is no real title available?)
• scientific article; zbMATH DE number 2157028 (Why is no real title available?)
• scientific article; zbMATH DE number 4001486 (Why is no real title available?)
• scientific article; zbMATH DE number 1390075 (Why is no real title available?)
• Satisfiability in Boolean logic (SAT problem) is polynomial
• STACS 2004
• Survey propagation: An algorithm for satisfiability
• The complexity of satisfiability problems
• An algorithm for approximating the satisfiability problem of high-level conditions
• A complexity analysis of the SAT problem
• Algorithms for four variants of the exact satisfiability problem
• Об одном методе построения следствий специального вида для систем булевых уравнений;On a method to construct special type corollaries for systems of Boolean equations
• Formula dissection: A parallel algorithm for constraint satisfaction

This page was built for publication:

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