Probabilistic performance of a heurisic for the satisfiability problem
An algorithm for the satisfiability problem (SAT) is presented and its probabilistic behavior is analyzed when combined with two other algorithms studied earlier. The analysis is based on an instance distribution which is parameterized to simulate a variety of sample characteristics. The algorithm dynamically assigns values to literals appearing in a given instance until a satisfying assignment is found or the algorithm ``gives up without determining whether or not a solution exists. It is shown that if n clauses are constructed independently from r Boolean variables, where the probability that a variable appears in a clause as a positive literal is p and as a negative literal is p, then almost all randomly generated instances of SAT are solved in polynomial time if \(p<0.4 \ln (n)/r\) or \(p>\ln (n)/r\) or \(p=c \ln (n)/r,\quad 0.4<c<1\) and \(\lim_{n,r\to \infty}n^{1-c}/r^{1-\epsilon}<\infty\) for any \(\epsilon >0\). It is also shown that if \(p=c \ln (n)/r,\quad 0.4<c<1\) and \(\lim_{n,r\to \infty}n^{1-c}/r=\infty\) then almost all randomly generated instances of SAT have no solution. Thus the combined algorithm is very effective in the probabilistic sense on instances of SAT that have solutions. The combined algorithm is effective in some limited sense in verifying unsatisfiability.
- scientific article; zbMATH DE number 4102824
- Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem
- Average Performance of Heuristics for Satisfiability
- Probabilistic analysis of satisfiability algorithms
- Probabilistic approach to the satisfiability problem
- A probabilistic study on the satisfiability problem
- scientific article; zbMATH DE number 3932819
- The probabilistic analysis of a greedy satisfiability algorithm
- scientific article; zbMATH DE number 1947423
- Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem
- A Computing Procedure for Quantification Theory
- Average time analyses of simplified Davis-Putnam procedures
- Correction to ``Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem
- scientific article; zbMATH DE number 3446196 (Why is no real title available?)
- On the complexity of regular resolution and the Davis-Putnam procedure
- Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem
- Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem
- Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem
- The Pure Literal Rule and Polynomial Average Time
- Solving satisfiability in less than \(2^ n\) steps
- Solving the satisfiability problem by using randomized approach
- On the occurence of null clauses in random instances of Satisfiability
- Experimental study on strategy of combining SAT algorithms
- An average case analysis of a resolution principle algorithm in mechanical theorem proving.
- Average case results for satisfiability algorithms under the random-clause-width model
- Complete on average Boolean satisfiability
- Probabilistic characterization of random Max r-Sat
- A randomized satisfiability procedure for arithmetic and uninterpreted function symbols
- Typical case complexity of satisfiability algorithms and the threshold phenomenon
- An exact and a randomized approach for the satisfiability problem
- Unique solution instance generation for the 3-satisfiability (3SAT) problem
- Satsisfiability and systematicity
- Probabilistic analysis of satisfiability algorithms
- scientific article; zbMATH DE number 3932819 (Why is no real title available?)
- scientific article; zbMATH DE number 3954272 (Why is no real title available?)
- Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem
- scientific article; zbMATH DE number 4102824 (Why is no real title available?)
- Experimental comparison of 2-satisfiability algorithms
- Elimination of Infrequent Variables Improves Average Case Performance of Satisfiability Algorithms
- scientific article; zbMATH DE number 1113991 (Why is no real title available?)
- scientific article; zbMATH DE number 1947423 (Why is no real title available?)
- The phase transition in random horn satisfiability and its algorithmic implications
- On the complexity of probabilistic trials for hidden satisfiability problems
- An algorithm for the satisfiability problem of formulas in conjunctive normal form
- Artificial Intelligence and Soft Computing - ICAISC 2004
- scientific article; zbMATH DE number 4003523 (Why is no real title available?)
- Average Performance of Heuristics for Satisfiability
- Analysis of Two Simple Heuristics on a Random Instance ofk-sat
- scientific article; zbMATH DE number 3894500 (Why is no real title available?)
- Theory and Applications of Satisfiability Testing
- Theory and Applications of Satisfiability Testing
- About a surprising computer program of Matthias Müller
- An algorithm for approximating the satisfiability problem of high-level conditions
- The probabilistic analysis of a greedy satisfiability algorithm
- A randomized satisfiability procedure for arithmetic and uninterpreted function symbols.
- Results related to threshold phenomena research in satisfiability: Lower bounds
- A new algorithm design technique for hard problems, building on methods of complexity theory
- A dual algorithm for the satisfiability problem
- Computational experience with an interior point algorithm on the satisfiability problem
- Heuristic-based backtracking relaxation for propositional satisfiability
- Probabilistic satisfiability: algorithms with the presence and absence of a phase transition
- Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem
- Probabilistic bounds and algorithms for the maximum satisfiability problem
This page was built for publication: Probabilistic performance of a heurisic for the satisfiability problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1115189)
