A Complexity Index for Satisfiability Problems
From MaRDI portal
Publication:4286227
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
polynomial algorithmsBoolean satisfiabilitysatisfiability problemsNP completenessconjunctive normal form
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
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
