Ich könnte dir die "theoretische Informatik Bibel": Introduction to Automata Theory Languages, and Computation" von Hopcraft und Ullman empfehlen.
Zumindest wenn es dir um Sachen wie NP-Vollständigkeit und unentscheidbarkiet geht.

Auf der Website zum Buch kannst du dir ja mal den Inhalt ansehen.