History [of cyclic tag systems] Cyclic tag systems were studied by Matthew Cook in 1994 in connection with working on the rule 110 cellular automaton for this book.

The set (a) below was announced by Roger Penrose in 1994; the slightly smaller set (b) was found by Matthew Cook as part of the development of this book.

NP completeness (see below ) was introduced by Stephen Cook in 1971 and Leonid Levin around the same time.

The general outline of what had to be done was fairly clear—but there were an immense number of details to be handled, and I asked a young assistant of mine named Matthew Cook to investigate them.

But I have been fortunate over the years to employ a variety of talented assistants, who have helped the project in many different ways: Eric Berg (project management, 2000–2001), Jason Cawley (historical and philosophical issues, 2001–2002 and before), Matthew Cook (technical content, particularly constructions and proofs, 1991–1998), Andrew de Laix (technical content and book production systems, 1998–2002), Matthew Frank (mathematical and historical issues, 2001–2002), Andrea Gerlach (fact finding and checking, 1999–2002), David Hillman (constructions and other technical content, 1997–2001), Scott Koranda (book production systems and project management, 1996–1998), Ed Pegg, Jr.