Finding Reductions Automatically

DOI10.1007/978-3-642-15025-8_10zbMath1287.68024OpenAlexW2110020743MaRDI QIDQ3586003

Michael S. Crouch, Neil Immerman, J. Eliot B. Moss

Publication date: 3 September 2010

Published in: Fields of Logic and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-15025-8_10

zbMATH Keywords

descriptive complexitySAT solverfirst-order reductionquantifier-free reduction

Mathematics Subject Classification ID

Other programming paradigms (object-oriented, sequential, concurrent, automatic, etc.) (68N19) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15)

Related Items

The QBF Gallery: behind the scenes

Uses Software

• MiniSat
• Cmodels
• Chaff
• SETL

Cites Work

• Unnamed Item
• Unnamed Item
• Elements of finite model theory.
• Answer set programming based on propositional satisfiability
• The complexity of satisfiability problems: Refining Schaefer's theorem
• Reducibility by algebraic projections
• Propositional semantics for disjunctive logic programs
• Undirected ST-connectivity in log-space
• Languages that Capture Complexity Classes
• On the Structure of Polynomial Time Reducibility
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Why are there so many loop formulas?
• Theory and Applications of Satisfiability Testing
• The complexity of satisfiability problems