A Complexity Index for Satisfiability Problems

DOI10.1137/S0097539792228629MaRDI QIDQ4286227zbMATH OpenOpenAlexWikidataFDO

Authors Endre Boros, Peter L. Hammer, Yves Crama, Michael 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 algorithmssatisfiability problemsBoolean satisfiabilityconjunctive normal formNP completeness

Mathematics Subject Classification ID

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

Recommendations

• The complexity of satisfiability problems
• The complexity of constraint satisfaction revisited
• Computational Complexity of Constraint Satisfaction
• Complexity of the satisfiability problem for a class of propositional schemata
• The complexity of minimal satisfiability problems
• scientific article; zbMATH DE number 1688380
• Mathematical Foundations of Computer Science 2005
• The complexity of satisfiability problems: Refining Schaefer's theorem
• Complexity of generalized satisfiability counting problems
• STACS 2004

Cited in

(27)

• Typical case complexity of satisfiability algorithms and the threshold phenomenon
• A perspective on certain polynomial-time solvable classes of satisfiability
• The Horn renamability, q-Horn and SLUR threshold for random \(k\)-CNF formulas
• Lean clause-sets: Generalizations of minimally unsatisfiable clause-sets
• A short note on some tractable cases of the satisfiability problem.
• Recognition of q-Horn formulae in linear time
• Variable and term removal from Boolean formulae
• On functional dependencies in q-Horn theories
• Satisfiability with index dependency
• Maximum renamable Horn sub-CNFs
• On connectedness of solutions to integer linear systems
• Complexity of partial satisfaction. II.
• Solving the resolution-free SAT problem by submodel propagation in linear time
• A complexity analysis of the SAT problem
• An artificial neural network satisfiability tester
• Bridging between 0/1 and linear programming via random walks
• scientific article; zbMATH DE number 3874957 (Why is no real title available?)
• Recognition of tractable satisfiability problems through balanced polynomial representations
• Trichotomy for integer linear systems based on their sign patterns
• A complete adaptive algorithm for propositional satisfiability
• On the Boolean connectivity problem for Horn relations
• Theory and Applications of Satisfiability Testing
• On perfect \(0,\pm 1\) matrices
• Power indices and easier hard problems
• A sharp threshold for the renameable-Horn and the \(q\)-Horn properties
• Investigations on autark assignments
• Satisfiability with index dependency

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

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