Survey of polynomial transformations between NP-complete problems

DOI10.1016/J.CAM.2011.02.018MaRDI QIDQ555184zbMATH OpenOpenAlexFDO

Authors Jianyong Qiao, Sumit K. Garg

Publication date 22 July 2011

Published in Journal of Computational and Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.cam.2011.02.018

zbMATH Keywords

surveycomputational complexityNP-completepolynomial reductionspolynomial transformations

Mathematics Subject Classification ID

Complexity and performance of numerical algorithms (65Y20)

Recommendations

• On limitations of transformations between combinatorial problems
• Reductions, completeness and the hardness of approximability
• Linearly-growing reductions of Karp's 21 NP-complete problems
• scientific article; zbMATH DE number 515731
• Approximation preserving reductions

Cites work

• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3225808 (Why is no real title available?)
• scientific article; zbMATH DE number 3302125 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• A comparison of polynomial time reducibilities
• Recursively enumerable sets of positive integers and their decision problems
• Survey of polynomial transformations between NP-complete problems
• The complexity of theorem-proving procedures

Cited in

(5)

• IS CAUSAL REASONING HARDER THAN PROBABILISTIC REASONING?
• Survey of polynomial transformations between NP-complete problems
• A useful transform of standard input data for a classical NP-complete problem
• A graph-transformational approach for proving the correctness of reductions between NP-problems
• On limitations of transformations between combinatorial problems

This page was built for publication: Survey of polynomial transformations between NP-complete problems

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