mathematics of the impossible: About this book

This is a book about computational complexity theory. However, it is perhaps sui generis for various reasons:

1. The presentation is also geared towards an algorithmic audience. Our default model is the RAM (Chapter 1), the standard model for algorithmic research. This is in contrast with other texts which focus on tape machines. I reduce RAM computation directly to quasi-linear 3SAT using sorting algorithms, and cover the relevant sorting algorithm. Besides typical reductions from the theory of NP completeness, I also present a number of other reductions, for example related to the 3SUM problem and the exponential-time hypothesis (ETH). This is done not only to showcase the wealth of settings, but because these reductions are central to algorithmic research. Also, I include a chapter on data structures, which are typically studied in algorithms yet omitted from complexity textbooks. I hope this book helps to reverse this trend; impossibility results for data structures squarely belong to complexity theory. Finally, a recurrent theme in the book is the power of restricted computational models. I expose surprising algorithms which challenge our intuition in a number of such models, including space bounded, boolean and algebraic circuits, and communication protocols.

2. The book contains a number of recent, exciting results which are not covered in available texts, including: space-efficient simulations (Chapter 7), connections between various small-depth circuit classes (section 8.2.3), catalytic computation (section 9.6), cryptography in NC0 (section 9.5), doubly-efficient proof systems (which have formed the basis of some deployed cryptographic systems) (section 10.5), simple constructions of expanders avoiding iterated recursion (Chapter 12), recent number-on-forehead communication protocols (section 13.4), succinct data structures (section 15.1.2), impossibility results for constant-depth algebraic circuits (Chapter 14), and natural-proof barriers that are informed by deployed cryptosystems (Chapter 16).

3. I also present several little-known but important results. This includes several simulations between models, the fact that RAMs with large registers can factor efficiently (Theorem 1.7), the result that time o(n log n) equals linear time on 1-tape machine (section 3.3.1), cosmological bounds (Theorem 3.8), the complexity of computing integers and its connections to factoring (section 14.2), and several results on pointer chasing section 13.4.1).

4. A number of well-known results are presented in a different way. Why? To demystify them and expose illuminating connections. Some of this was discussed above in 1. In addition, unlike other texts where they appear later, here I present circuits and randomness right away, and weave them through the narrative henceforth. For example, the exposition of alternation (Chapter 6) is through the lens of the circuit model. That exposition also emphasizes pseudorandom generators and thus ties with the later Chapter 11 on pseudorandomness. And in that chapter, the BIG-HIT generator is used to give a streamlined construction of pseudorandom generators from hard functions, avoiding some of the steps of previous constructions. Finally, reductions are presented before completeness rather than later as in most texts. This, I believe, demystifies their role and leads to a transparent exposition as stand-alone results.

5. This book challenges traditional assumptions and viewpoints. For example, I discuss my reasons for not believing P ≠ NP. In particular, I catalog and contextualize for the first time conjectures in complexity lower bounds which were later disproved (Chapter 17). Also, I emphasize that several available impossibility results may be strong rather than weak as commonly believed because they fall just short of proving major separations (e.g. section 7.3), and I expose the limitations of standard tools such as the hard-core set lemma (section 11.2.2). Finally, I include a series of historical vignettes which put key results in perspective.

I made several other choices to focus the exposition on the important points. For example I work with partial (as opposed to total) functions by default, which streamlines the presentation of several results, such as the time hierarchy (section 3.3), and eliminates NP-intermediate problems (Exercise 5.3). To put results in context I routinely investigate what happens under slightly different assumptions. Finally, I present proofs in a top down fashion rather than bottom up, starting with the main high-level ideas and then progressively opening up details, and I try to first present the smallest amount of machinery that gives most of the result.

This book is intended both as a textbook and as a reference book. The intended audience includes students at all levels, and researchers, in both computer science and related areas such as mathematics, physics, data science, and engineering. The text is interspersed with exercises which serve as quick concept checks, for example right after a definition. More advanced problems are collected at the end of each chapter. Solutions or hints for both exercises and problems are provided as separate manuals. I assume no background in theory of computation, only some mathematical maturity as can arise for example from typical introductory courses in discrete mathematics. All other mathematical background is covered in Appendix A.

The book can be used in several different types of courses.

• For an introductory course in theory of computation, suitable for a beginner undergraduate student, one can cover Chapters 1 to 5. At the same time the text can expose the interested students to more advanced topics, and stimulate their critical thinking.

• For a broader course in complexity, suitable for advanced undergraduate students or for graduate students, one can add Chapters 6 to 10. Such a course can be supplemented with isolated topics from Chapters 11 to 16. For example, in my offerings of cross-listed undergraduate/graduate PhD complexity theory, I typically cover Chapters 1 to 10 and then one or two select chapters from 11 to 16. The pace is about one chapter a week, and I ask the students to attempt all exercises.

• For a special-topics course or seminar one can use Chapters 11 to 16. One possibility, which I tested, is covering all these chapters.

Chapters 1 to 10 are best read in order. Chapters 11 to 16 have fewer dependencies and can be read more or less in any order.

I hope this text will keep the reader engaged and serve as an invitation and guide to the mysterious land of complexity, until the reader stands at its frontier, gazing into the vast unknown.