On the occurence of null clauses in random instances of Satisfiability

DOI10.1016/0166-218X(90)90054-GzbMATH Open0781.68067MaRDI QIDQ1208481FDOQ1208481

Authors: John V. Franco 

Publication date: 16 May 1993

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Recommendations

• Probabilistic performance of a heurisic for the satisfiability problem
• Elimination of Infrequent Variables Improves Average Case Performance of Satisfiability Algorithms
• The probability of pure literals
• The Pure Literal Rule and Polynomial Average Time
• Exponential Average Time for the Pure Literal Rule

zbMATH Keywords

satisfiabilityprobabilistic model

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Classical propositional logic (03B05)

Cites Work

• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• Elimination of Infrequent Variables Improves Average Case Performance of Satisfiability Algorithms
• The Pure Literal Rule and Polynomial Average Time
• Polynomial-average-time satisfiability problems
• Exponential Average Time for the Pure Literal Rule

This page was built for publication: On the occurence of null clauses in random instances of Satisfiability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1208481)