An exponential lower bound for the pure literal rule

DOI10.1016/0020-0190(88)90028-2zbMATH Open0646.68061OpenAlexW2076029782MaRDI QIDQ1104093FDOQ1104093

Authors: Khaled M. Bugrara, Paul Walton jun. Purdom 

Publication date: 1988

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(88)90028-2

Recommendations

• Exponential Average Time for the Pure Literal Rule
• The Pure Literal Rule and Polynomial Average Time
• The probability of pure literals
• scientific article; zbMATH DE number 437557
• New worst-case upper bounds for SAT

zbMATH Keywords

average time analysisDavis-Putnam procedurepure literal rule

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites Work

• Title not available (Why is that?)
• A machine program for theorem-proving
• Corrigendum to ``Average time analyses of simplified Davis-Putnam procedures
• The Pure Literal Rule and Polynomial Average Time
• Polynomial-average-time satisfiability problems

Cited In (4)

• Exponential Average Time for the Pure Literal Rule
• The complexity of pure literal elimination
• The Pure Literal Rule and Polynomial Average Time
• A Variational Method for Analysing Unit Clause Search

This page was built for publication: An exponential lower bound for the pure literal rule

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