Experiments with reduction finding

DOI10.1007/978-3-642-39071-5_15MaRDI QIDQ5326462zbMATH OpenOpenAlexFDO

Authors Charles Jordan, Łukasz Kaiser

Publication date 5 August 2013

Published in Theory and Applications of Satisfiability Testing – SAT 2013 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-39071-5_15

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Automatic Evaluation of Reductions between NP-Complete Problems
• Fixed-parameter tractable reductions to SAT
• Reductions, completeness and the hardness of approximability
• On O(Tlog T) reduction from RAM computations to satisfiability
• Analysis of a new reduction calculus for the satisfiability problem

Cited in

(12)

• Lower bound techniques for QBF expansion
• Synthesis of a DNF formula from a sample of strings using Ehrenfeucht-Fraïssé games
• On distinguishing sets of structures by first-order sentences of minimal quantifier rank
• Solving QBF with counterexample guided refinement
• Computing smallest MUSes of quantified Boolean formulas
• Incremental determinization
• The QBF Gallery: behind the scenes
• scientific article; zbMATH DE number 7228403 (Why is no real title available?)
• REDUCTION PROBLEMS IN EXPERIMENTAL INVESTIGATIONS
• On finding a first-order sentence consistent with a sample of strings
• New methods for proving the impossibility to solve problems through reduction of problem spaces
• Specification and automatic verification of computational reductions

This page was built for publication: Experiments with reduction finding

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