Exponential Average Time for the Pure Literal Rule

DOI10.1137/0218028MaRDI QIDQ3832061zbMATH OpenOpenAlexFDO

Authors Khaled M. Bugrara, Youfang Pan, Paul Walton jun. Purdom

Publication date 1989

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0218028

zbMATH Keywords

average timebacktrackingcombinatorial searchDavis-PutnamNP-completepure literal rulesatisfiabilitysearching

Mathematics Subject Classification ID

Mechanization of proofs and logical operations (03B35) Data structures (68P05) Information storage and retrieval of data (68P20) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• The Pure Literal Rule and Polynomial Average Time
• An exponential lower bound for the pure literal rule
• Polynomial-average-time satisfiability problems
• CNF-Satisfiability Test by Counting and Polynomial Average Time
• scientific article; zbMATH DE number 30299

Cited in

(10)

• 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
• An average case analysis of a resolution principle algorithm in mechanical theorem proving.
• Correction to ``Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem
• The Pure Literal Rule and Polynomial Average Time
• CNF-Satisfiability Test by Counting and Polynomial Average Time
• scientific article; zbMATH DE number 30299 (Why is no real title available?)
• Average Time Analysis of Clause Order Backtracking
• A Variational Method for Analysing Unit Clause Search

This page was built for publication: Exponential Average Time for the Pure Literal Rule

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