On the occurence of null clauses in random instances of Satisfiability

DOI10.1016/0166-218X(90)90054-GzbMath0781.68067MaRDI QIDQ1208481

John V. Franco

Publication date: 16 May 1993

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

zbMATH Keywords

satisfiabilityprobabilistic model

Mathematics Subject Classification ID

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

Cites Work

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

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