A Complexity Index for Satisfiability Problems
DOI10.1137/S0097539792228629zbMATH Open0793.90038OpenAlexW1965913970WikidataQ59560955 ScholiaQ59560955MaRDI QIDQ4286227FDOQ4286227
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
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
polynomial algorithmssatisfiability problemsBoolean satisfiabilityconjunctive normal formNP completeness
Abstract computational complexity for mathematical programming problems (90C60) Artificial intelligence (68T99) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Boolean programming (90C09)
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
- On connectedness of solutions to integer linear systems
- Maximum renamable Horn sub-CNFs
- Complexity of partial satisfaction. II.
- A complexity analysis of the SAT problem
- Solving the resolution-free SAT problem by submodel propagation in linear time
- An artificial neural network satisfiability tester
- Bridging between 0/1 and linear programming via random walks
- Title not available (Why is that?)
- 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
- Theory and Applications of Satisfiability Testing
- On the Boolean connectivity problem for Horn relations
- 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)
