Polynomial-average-time satisfiability problems
From MaRDI portal
Publication:1095678
DOI10.1016/0020-0255(87)90003-XzbMath0632.68086MaRDI 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
68Q25: Analysis of algorithms and problem complexity
Related Items
An exponential lower bound for the pure literal rule, 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, An exact algorithm for the constraint satisfaction problem: Application to logical inference, An average case analysis of a resolution principle algorithm in mechanical theorem proving., Branch-and-cut solution of inference problems in propositional logic, Average running time analysis of an algorithm to calculate the size of the union of Cartesian products., Average Running Time Analysis of an Algorithm to Calculate the Size of the Union of Cartesian Products
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
