The appreciation of complexity theory outside of theoretical computer science is largely due to the notoriety of open questions such as 1–4. Of these, Open Question 1 – henceforth \(\textbf{P} \neq \textbf{NP}?\) – has attracted the greatest attention. Along with long standing unresolved questions from pure and applied mathematics such as the Riemann Hypothesis and the Hodge Conjecture, it is the subject of a major prize competition – i.e. the Millennium Problems (Cook 2006). It is also frequently the focus of survey articles and popular expositions – e.g. (Sipser 1992), (Fortnow 2009), and (Fortnow 2013).