Introduction to complexity theory
Alexander K. Hartmann, Martin Weigt · 2005
This chapter contains sections titled: Turing machines Church's thesis Languages The halting problem Class P Class NP Definition of NP-completeness NP-complete problems Proving NP-completeness 3-SAT Vertex cover Worst-case vs. typical-case complexity Bibliography