- M.Garey and D.Johnson. Computers and Intractability. A Guide to the Theory of
NP-Completeness. Freemann, San Francisco, 1979.
A classic book explaining the concepts of NP-Completeness and problem difficulty.
- C.M. Papadimitriou.Computational Complexity. Addison-Wesley, Reading, Massachusetts, 1994
- C.M. Papadimitriou and K.Steiglitz. Combinatorial Optimization: Algorithms and Complexity. Prentice Hall, Englewood Cliffs, NJ, 1982.
Two more good books describing the theory of what makes problems hard.
- F. Neumann and C.~Witt. Bioinspired Computation in Combinatorial Optimization: Algorithms and Their Computational Complexity. Springer, Natural Computing Series, 2010.
Relates bio-inspired algorithms such as evolutionary algorithms to computational complexity