"Komplexitätstheorie" von Ingo Wegener ist das beste deutsche Buch zum Thema das ich bisher gelesen habe. Das Buch ist sehr gut strukturiert und, für die Möglichkeiten die einem der Inhalt lässt, auch verständlich geschrieben. Insbesondere finden sich in dem Buch viele Beispiele, insb. viele wirklich wichtige NP-vollständige Probleme und entsprechende Reduktionen als Beweis für die Komplexität. Das hat zwei Effekte, zum einen kann man Reduktionen üben und nachvollziehen, zum anderen hat man viele wichtige Probleme auf die man in der Praxis trifft bereits als NP-vollständig kennengelernt.
Natürlich ist das ganze sehr theoretisch und dementsprechend dauert das Nachvollziehen und Verstehen (der Formeln bzw. Konzepte) seine Zeit, man sollte nicht den Fehler machen davon auszugehen, den Inhalt nach dem ersten Durchlesen/-arbeiten zu können! Und wenn man ihn versteht, dann liegt es in der Natur der Sache, dass man jetzt nicht sofort jedes Problem einfach klassifizieren kann, denn dazu erfordert es doch ziemlich viel Geschick, etwas Übung und Glück ;) (und wenn man Pech hat ist es quasi unmöglich). Hilfreich sind an der Stelle allerdings einige Techniken die erläutert werden, z.B. die Lückentechnik.
Das Buch eignet sich gut zur Begleitung entsprechender Vorlesungen. Sich den Inhalt ohne Übungsgruppen bzw. Möglichkeiten zum Nachfragen/Diskutieren anzueignen halte ich für eher schwierig - allerdings nicht unmöglich.