Density condensation of Boolean formulas

DOI10.1016/j.dam.2006.04.014zbMath1106.94026OpenAlexW2007136448MaRDI QIDQ860385

Takashi Horiyama, Kazuo Iwama, Youichi Hanatani

Publication date: 9 January 2007

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

Full work available at URL: https://doi.org/10.1016/j.dam.2006.04.014

zbMATH Keywords

computational complexityBoolean formulasSAT algorithmsdensity condensation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (1)

The Relation Between Complete and Incomplete Search

Cites Work

• Unnamed Item
• Solving satisfiability in less than \(2^ n\) steps
• The complexity of facets resolved
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• A Computing Procedure for Quantification Theory
• A machine program for theorem-proving

This page was built for publication: Density condensation of Boolean formulas