scientific article

zbMath0673.90074MaRDI QIDQ3827800

John V. Franco

Publication date: 1984

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

probabilistic analysissatisfiability problemaverage complexitypolynomial timeprocedureDavis-Putnampure literal heuristic

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Boolean programming (90C09)

Related Items

Polynomial-average-time satisfiability problems, The expected complexity of analytic tableaux analyses in propositional calculus. II, An average case analysis of a resolution principle algorithm in mechanical theorem proving., Some results and experiments in programming techniques for propositional logic, Threshold saturation in spatially coupled constraint satisfaction problems, Probabilistic bounds and algorithms for the maximum satisfiability problem, Rigorous results for random (\(2+p)\)-SAT, A threshold for unsatisfiability