The complexity of pure literal elimination

DOI10.1007/S10817-005-9008-8zbMATH Open1109.68050OpenAlexW2055823534MaRDI QIDQ862401FDOQ862401

Authors: Jan Johannsen 

Publication date: 24 January 2007

Published in: Journal of Automated Reasoning (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10817-005-9008-8

Recommendations

• An exponential lower bound for the pure literal rule
• Clause elimination procedures for CNF formulas
• scientific article; zbMATH DE number 1678383
• The probability of pure literals
• The Pure Literal Rule and Polynomial Average Time

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• BerkMin: A fast and robust SAT-solver
• Title not available (Why is that?)
• A machine program for theorem-proving
• New problems complete for nondeterministic log space
• New methods for 3-SAT decision and worst-case analysis
• Undirected ST-connectivity in log-space
• Symmetric space-bounded computation
• Theory and Applications of Satisfiability Testing
• Space-bounded reducibility among combinatorial problems
• Title not available (Why is that?)
• STACS 2004

Cited In (2)

• Title not available (Why is that?)
• Title not available (Why is that?)

Uses Software

• Chaff
• BerkMin
• semprop

This page was built for publication: The complexity of pure literal elimination

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