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

NP-completesatisfiabilitybacktrackingcombinatorial searchsearchingpure literal ruleaverage timeDavis-Putnam

Mathematics Subject Classification ID

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

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

(9)

• Correction to ``Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem
• An exponential lower bound for the pure literal rule
• The Pure Literal Rule and Polynomial Average Time
• Average Time Analysis of Clause Order Backtracking
• CNF-Satisfiability Test by Counting and Polynomial Average Time
• Solving the satisfiability problem by using randomized approach
• An average case analysis of a resolution principle algorithm in mechanical theorem proving.
• On the occurence of null clauses in random instances of Satisfiability
• 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)