Automatic Evaluation of Reductions between NP-Complete Problems

DOI10.1007/978-3-319-09284-3_30MaRDI QIDQ3192087zbMATH OpenOpenAlexFDO

Authors Carles Creus, Pau Fernández, Guillem Godoy

Publication date 26 September 2014

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-09284-3_30

zbMATH Keywords

NP-completenessreductionsSAT applicationself-learning

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• Comparing reductions to NP-complete sets
• Comparing Reductions to NP-Complete Sets
• Autoreducibility of NP-complete sets
• scientific article; zbMATH DE number 3889514
• scientific article; zbMATH DE number 4126690
• scientific article; zbMATH DE number 915981
• Autoreducibility of NP-complete sets under strong hypotheses
• Propositional proofs and reductions between NP search problems
• Measuring the complexity of reductions between equivalence relations
• scientific article; zbMATH DE number 1759426

Cited in

(2)

• Experiments with reduction finding
• A graph-transformational approach for proving the correctness of reductions between NP-problems

This page was built for publication: Automatic Evaluation of Reductions between NP-Complete Problems

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