Polynomial-average-time satisfiability problems

DOI10.1016/0020-0255(87)90003-XzbMath0632.68086OpenAlexW1995067748MaRDI QIDQ1095678

Cynthia A. Brown, Paul Walton jun. Purdom

Publication date: 1987

Published in: Information Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0255(87)90003-x

zbMATH Keywords

satisfiabilitybacktrackingaverage timerandom predicate

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

An average case analysis of a resolution principle algorithm in mechanical theorem proving., Branch-and-cut solution of inference problems in propositional logic, An exponential lower bound for the pure literal rule, Average running time analysis of an algorithm to calculate the size of the union of Cartesian products., Solving the satisfiability problem by using randomized approach, On the occurence of null clauses in random instances of Satisfiability, On matijasevitch's nontraditional approach to search problems, Average Running Time Analysis of an Algorithm to Calculate the Size of the Union of Cartesian Products, An exact algorithm for the constraint satisfaction problem: Application to logical inference

Cites Work

• Unnamed Item
• Unnamed Item
• Average time analyses of simplified Davis-Putnam procedures
• Solving satisfiability in less than \(2^ n\) steps
• Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem
• An Analysis of Backtracking with Search Rearrangement
• Solving Satisfiability with Less Searching
• The Pure Literal Rule and Polynomial Average Time
• Applications of a Planar Separator Theorem
• An Average Time Analysis of Backtracking
• A $T = O(2^{n/2} )$, $S = O(2^{n/4} )$ Algorithm for Certain NP-Complete Problems
• Estimating the Efficiency of Backtrack Programs
• A Computing Procedure for Quantification Theory