Most optimization textbooks do not cover the concept of NP-hardness. Some examples include:

  • "Convex optimization" by Boyd and Vandenberghe

  • "Numerical Optimization" by Nocedal and Wright

  • "An Introduction to Optimization" by Chong and Zak

and half a dozen more well-known optimization textbooks.

Yet, in discussion on optimization problem, I frequently see people referring to some problems as NP-hard (or not).

The definition I've learned regarding complexity theory started from things like language, string, Kleene star operator, Turing machines, which are also things that are not mentioned in typical optimization textbooks.

So is there some type of reference in bridging the gap between complexity theory and optimization?


1 Answer 1


In my opinion, monographs on approximation algorithms come closest to what you are seeking:

If you are still struggling with understanding NP-hardness theory, the classic monograph is:

  • Computers and Intractability, by Michael Garey and David S. Johnson.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.