The book extends to space complexity classes, discussing PSPACE complete problems, NL-complete problems, and proving that NL=coNL.Finally, the text ventures beyond NP-completeness, discussing Ladner’s construction of non-NPC sets, randomized complexity classes, and concepts such as BPP and the polynomial hierarchy.