Polynomial-average-time satisfiability problems
From MaRDI portal
Publication:1095678
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
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
