Historical surveys of the early development of computational complexity theory by the Western and Soviet schools are respectively provided in (Fortnow and Homer 2003) and (Trakhtenbrot 1984). (Wagner and Wechsung 1986) and (Emde Boas 1990) provide detailed treatments of machine models, simulation results, the status of the Invariance Thesis, and the distinction between the first and second machine classes. Basic topics in complexity theory are presented in semi-popular form in (Allender and McCartin 2000), (Harel 2006), (Cook 2012), and (Fortnow 2013). Introductory presentations can also be found in many general undergraduate textbooks on theoretical computer science such as (Hopcroft and Ulman 1979), (Lewis and Papadimitriou 1998), and (Sipser 2006). More advanced textbook treatments of complexity theory include (Papadimitriou 1994), (Du and Ko 2000), (Hemaspaandra and Ogihara 2002), (Arora and Barak 2009), and (Goldreich 2010). Many of these books cover topics which are not surveyed here but which may be of interest to philosophers – e.g. randomized algorithms, probabilistically checkable proofs, natural proofs, zero-knowledge proofs, and interactive proof systems. (Van Leeuwen 1990) contains survey articles on several complexity-related topics. The standard reference on \(\textbf{NP}\)-completeness remains (Garey and Johnson 1979) which contains a list of over 300 \(\textbf{NP}\)-complete problems. A similar reference on \(\textbf{P}\)-completeness is (Greenlaw, Hoover, and Ruzzo 1995). Structural complexity theory – i.e. the study of different reduction notions and the corresponding degree structures – is developed in (Balcázar, Diaz, and Gabarró 1988) and (Odifreddi 1999). Textbook treatments of proof complexity, descriptive complexity, and bounded arithmetic are respectively provided by (Cook and Nguyen 2010), (Immerman 1999), and (Hájek and Pudlák 1998). (Moore and Mertens 2011) and (Aaronson 2013b) also provide recent philosophically-oriented surveys of complexity theory.