Complexity Theory
😉
Here are my thoughts and embedded scribes of the computational complexity course taught in UW–Madison in 2024 Spring, taught by the Steenbock Professor, Gödel Prize winner Jin-Yi Cai.
It is my honor to take his class.
Disclaimer: This article and embedded scribes definitely contain errors in tiny details though I have tried moderate efforts.
Preamble: What and Why?
Unlike the field of algorithms, complexity theory does not usually focus on any specific algorithm for any specific problem, but try to ask some meta questions:
- can problems be categorized in different classes, based on their intrinsic complexity?
- if yes, what are the relationship to these classes?
Complexity theory as to algorithms is similar to the case in calculus, where we compare theorems on a class of functions (e.g. the set of uniformly continuous functions is properly contained in the set of continuous functions) to tricks applied to specific function (e.g. substitution rules for certain integral).
It is a subject studying the meta questions instead of specific problems.
The birth of this subject comes from whether we can decide whether a problem has a solution, i.e. the Entscheidungsproblem, and efficiently.
As we are thinking the complexity of problems in a more abstract and meta way, we can create some powerful and even unrealistic models to capture the real world problems. One of the beauties in complexity theory is that such models usually have non-trivial deep connections with each other, and sometimes the proofs are succinct and elegant.
Even though one can realize the beauty and power of the abstract theory some time, it is still important to take some glances at the examples (realistic prevailing problems) from time to time.
In addition to pure intellectual fun, computational complexity plays an central role in computing, and lays theoretical foundations for many potential applications, including cryptography, quantum computing, efficient algorithm design like approximation.
However, I do not recommend those who do not have strong mathematical background or interest in mathematics and TCS, or with more intent to play with applications, to rush into the study of this field. This subject can be intellectually harder than most of the CS fields I have learned, but to not discourage readers too much, it is also more rewarding every time figuring something out.
Preliminaries (especially )
The prerequisite for these scribes is primarily to understand Turing machine, especially non-deterministic Turing machine, and complexity classes (e.g. ). It is better to understand the proof of a universal deterministic Turing machine simulation using time complexity.
Here are some resources to boost up:
- The videos for lecture 5 & 6 in the MIT open course 18.404/6.840 Theory Of Computation gives a good introduction to the Turing machine topics
- Section 1.1, 1.2, 1.3 and 2.1 in Prof. Jin-Yi Cai’s draft book provides a good start to some basics including Turing machine and complexity classes, especially motivation of the birth in complexity theory
- Section 1.A in Prof. Sanjeev and Boaz's draft book provides a complete proof of such a universal simulation in time
Hierarchy Theorem
Then, we can take a look at the relationship among these relatively simple complexity classes
Hierarchy Theorem
- The time hierarchy theorem for has not covered here so far
- Informally speaking, the hierarchy refers to the fact that there are some gap between each hierarchy (or say each hierarchy is (expected to be) properly contained within another higher hierarchy, rather than (expecting to) collapse to the same complexity class.
- For example, collapse to the same class by definition; while by efficient universal simulation, we known that the gap exists if
- We can see that space and time complexity for both deterministic and non-deterministic Turing machine do not collapse to the same level; while we will see another kind of complexity classes, called polynomial hierarchy whose definition is the union of a collection of classes, that the collapse is not yet known.
A Taste of Random Algorithm
Let us digress a bit. After witnessing the beauty of directed graph accessibility problem (GAP) using nondeterministic log space. To have a taste of random algorithms in deterministic log space, by looking at a weaker configuration of the GAP problem
Log Space Undirected Graph Accessibility Algorithm:
- USTCONN
- this problem actually has a stronger result that it can be solved with deterministic log space, i.e. , but the derandomization technique is beyond current scope
New Power: Oracles
Let us back on the topic, finding new complexity classes and discussing their relationships. Here, we are going to
- take a look at oracles, another special capabilities as magical as non-determinism in the ,
- and define the polynomial hierarchy (),
- and see if it separates and ;
- we will even touch another computation model, circuits, as we see the limit of our current methods.
It is amazing to see that the equivalent definitions of on either quantifier-base or relativization-base, since we should be philosophically worried about the realistic counterpart of our made-up concept, the oracle, whereas this shows that there is some connection to the second-order logic, a natural, well discovered topic.
Though a direct separation is not yet known, Cai improved Yao’s work, stating that separating from by almost all oracles.
Computing with Circuits (WIP)
uniformity defined on non-uniform model of computation is a bridge between circuits and Turing machine for recursive languages.
non-uniform circuits for non-recursive languages such as halting problem (?)
best-known circuit complexity for common computations, e.g. addition, multiplication, solving linear systems
width vs. depth vs. size → width 5 circuit
some other results in Cai’s draft book
relationship between set (e.g. recursive enumerable set) and complexity classes
examples of languages accepted by sub-log-space TM
motivation to find lower bound for circuits with super-linear size, since Shannon proved almost all circuits are of size, also a potential solution to vs. problem by proving the super-linear lower bound for any problem (however, theorists cannot make much progress so far).
two equal definitions:
- languages decided by poly-sized circuit families
- languages decided by poly-time TM with poly-sized advice
One of the most interesting reasons that P/poly is important is the property that if NP is not a subset of P/poly, then P ≠ NP. This observation was the center of many attempts to prove P ≠ NP. It is known that for a random oracle A, NPA is not a subset of PA/poly with probability 1.[1]
Karp-Lipton Theorem
Probabilistic Turing Machine (WIP)
Let us take a look at another kind of computing model by introducing randomness.
Here, we want to know does randomness help improve the efficiency or not, though the following statement is still an open question (similar in ):
Intersection of PP
Toda’s Theorem
Interactive Proof System (WIP)
, ,
Special Topic
This year, Avi Wigderson won the Turing Prize, notably for one of his seminal contributions to random complexity. Along with interest in understanding some fundamental properties of randomness, I decided to take his influential paper, Hardness vs Randomness, coauthored with Noam Nisan in late 1980s, as the topic for my term project report.
It turns out that in addition to the tight connections between randomness and hardness, they also play an essential role in the field of complexity theory, having deep connections with other topics we have mentioned so far. As stated in the report, I enjoy the the astonishing beauty for math and theoretical computer science, because of its elegance yet powerful results that connects many things, which at the first glance are not trivial or even weird, but finally turns out to share the common traits.
The acknowledgment is stated at the end of this term project report.