Survey of polynomial transformations between NP-complete problems

DOI10.1016/j.cam.2011.02.018zbMath1220.65193OpenAlexW2022173437MaRDI QIDQ555184

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)

Related Items (2)

IS CAUSAL REASONING HARDER THAN PROBABILISTIC REASONING? ⋮ Survey of polynomial transformations between NP-complete problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Survey of polynomial transformations between NP-complete problems
• A comparison of polynomial time reducibilities
• The complexity of theorem-proving procedures
• Recursively enumerable sets of positive integers and their decision problems

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