A Complexity Index for Satisfiability Problems

DOI10.1137/S0097539792228629zbMath0793.90038OpenAlexW1965913970WikidataQ59560955 ScholiaQ59560955MaRDI QIDQ4286227

Peter L. Hammer, Endre Boros, Yves Cramer, Michael E. Saks

Publication date: 16 August 1994

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539792228629

zbMATH Keywords

polynomial algorithmsBoolean satisfiabilitysatisfiability problemsNP completenessconjunctive normal form

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Boolean programming (90C09) Artificial intelligence (68T99) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (19)

Recognition of \(q\)-Horn formulae in linear time ⋮ On perfect \(0,\pm 1\) matrices ⋮ Variable and term removal from Boolean formulae ⋮ On the Boolean connectivity problem for Horn relations ⋮ An artificial neural network satisfiability tester ⋮ Lean clause-sets: Generalizations of minimally unsatisfiable clause-sets ⋮ Trichotomy for integer linear systems based on their sign patterns ⋮ Maximum renamable Horn sub-CNFs ⋮ Recognition of tractable satisfiability problems through balanced polynomial representations ⋮ Trichotomy for the reconfiguration problem of integer linear systems ⋮ Solving the resolution-free SAT problem by submodel propagation in linear time ⋮ A complete adaptive algorithm for propositional satisfiability ⋮ Investigations on autark assignments ⋮ The Horn renamability, q-Horn and SLUR threshold for random \(k\)-CNF formulas ⋮ A short note on some tractable cases of the satisfiability problem. ⋮ A sharp threshold for the renameable-Horn and the \(q\)-Horn properties ⋮ Typical case complexity of satisfiability algorithms and the threshold phenomenon ⋮ A perspective on certain polynomial-time solvable classes of satisfiability ⋮ On functional dependencies in \(q\)-Horn theories

This page was built for publication: A Complexity Index for Satisfiability Problems