Sometimes I read a book on optimization and the author states (without proof) that finding a certain solution to the (non-convex) optimization problem is NP hard.
I've learned about complexity theory in the past through a course in CS, and I remember we started by alphabets, language, string, certificate, Turing machine, and sets like $\Sigma^\star$ (forgot what they called - Ok apparently they are Kleene star operator)
http://www.cs.toronto.edu/~sacook/csc463h/notes/np_463.pdf https://cs.uwaterloo.ca/~watrous/CS360.Spring2017/Lectures/19.pdf
None of these notions ever appears in optimization literature.
How is there such a gap between the usage of complexity theory between these two fields?
Can anyone recommend a reference that explains complexity theory in the context of optimization?
There is a book called Network flows: theory, algorithms and applications by Ahuja, Magnanti and Orlin. In its appendix B NP-Completeness and NP-Hardness are introduced. I haven't learned the complexity theory in the CS way, so I don't know exactly how different this is from that in CS. But since this book mainly talks about optimization, I believe it will be helpful to you.