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

Boolean satisfiabilityconjunctive normal formNP completenesspolynomial algorithmssatisfiability problems

Mathematics Subject Classification ID

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

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)

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

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)