Nested satisfiability

DOI10.1007/BF02983372zbMath0691.68040arXivcs/9301111OpenAlexW2913068454MaRDI QIDQ582905

Donald E. Knuth

Publication date: 1990

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/cs/9301111

zbMATH Keywords

bipartite graphsatisfiability problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (12)

Backdoors to Satisfaction ⋮ A CNF Class Generalizing Exact Linear Formulas ⋮ Optimization and probabilistic satisfiability on nested and co-nested formulas ⋮ On exact selection of minimally unsatisfiable subformulae ⋮ Solving the resolution-free SAT problem by submodel propagation in linear time ⋮ New tractable classes for default reasoning from conditional knowledge bases ⋮ Satisfiability of mixed Horn formulas ⋮ The complexity of the falsifiability problem for pure implicational formulas ⋮ Selecting and covering colored points ⋮ On Some Aspects of Mixed Horn Formulas ⋮ Planar 3-SAT with a clause/variable cycle ⋮ Satisfiability of co-nested formulas

Cites Work

• Planar Formulae and Their Uses

This page was built for publication: Nested satisfiability