Linearly-growing reductions of Karp's 21 NP-complete problems

DOI10.3934/naco.2018001zbMath1416.68078arXiv1902.10349MaRDI QIDQ1713202

Peng Zhang

Publication date: 24 January 2019

Published in: Numerical Algebra, Control and Optimization (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1902.10349

zbMATH Keywords

computational complexity; integer programming; reduction; NP-completeness; Karp's problems; linear orbit

Mathematics Subject Classification ID

90C10: Integer programming

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)