Finding Reductions Automatically

DOI10.1007/978-3-642-15025-8_10MaRDI QIDQ3586003zbMATH OpenOpenAlexFDO

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

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

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

Recommendations

• Simplifying reductions
• Reducing the complexity of reductions
• scientific article; zbMATH DE number 1559593
• Automata for reduction properties solving
• Automatic Generation of Optimal Reductions of Distributions
• Publication:4934278
• scientific article; zbMATH DE number 3982555
• scientific article; zbMATH DE number 1047677
• scientific article; zbMATH DE number 2165788
• Algorithm of finding the best reduction based on reduction significance

Cites work

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

Cited in

(3)

• The QBF Gallery: behind the scenes
• Automatic Generation of Optimal Reductions of Distributions
• Toward automating the discovery of decreasing measures

Describes a project that uses

Uses Software

• SETL
• Chaff
• Cmodels
• MiniSat

This page was built for publication: Finding Reductions Automatically

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