The Descriptive Complexity of Solutions
A circuit based model of descriptive complexity
Andrey Kolmogorov was one of the greatest mathematicians of the last century. He created whole new areas of mathematics, he created new directions in existing areas, and he solved long standing open problems.
Today I wish to talk about a problem, that is related to his notion of complexity of a string—Kolmogorov Complexity. The problem I am interested is a natural problem, but would have strong consequences if we could solve it.
Kolmogorov is famous for his model of the complexity of a string as the length of the shortest program that can generate the string. Thus, the string of length
has complexity , while a “random” string
has complexity close to .
One of Kolmogorov’s great results was the partial solution of Hilbert’s Thirteenth problem, which was completed by his great student Vladimir Arnold. The final result was again done by Kolmogorov. He is reported to have said that proving this theorem was one of the most technically challenging proofs of his entire career.
This remarkable result it shows that conventional wisdom can be wrong, since David Hilbert appeared to believe that his Thirteenth problem would go the other way. There is some issue of exactly what Hilbert intended as the statement—so it is unclear if conventional wisdom was or was not overturned.
The final theorem that was proved by Kolmogorov states:
Theorem: For each , there exists continuous functions such that every continuous function is represented as
where the are continuous functions.
The import of the theorem is that for continuous functions there is no function of many variables. Note, the theorem shows that any function of variables can be expressed using only unary functions and addition. The only multi-variable function needed is addition, which seems surprising.
Let’s turn to talking about the complexity of strings from a slightly different point of view.
A Classic Problem
Let me introduce our complexity notion by looking at the problem of solving a linear system of equations,
where is a by integer matrix and is an integer vector. This is, of course, a classic problem: find an so that (1) is true, if one exists.
For this classic problem much is known, yet some questions remain open:
- The problem is in polynomial time—use Gaussian elimination, with some care. See my earlier post on the bits required for solving linear systems.
- The problem is in . That is a linear system can be solved with polynomial processors in time.
- The problem is also easily seen to be in , the class of problems that are reducible to the determinant.
- It is not known if the problem lies in lower complexity classes such as .
How Do We Describe A String?
Instead of Kolmogorov’s general notion of the complexity of a string, we will use a particular notion based on circuits. Suppose that is a circuit and is a string. Say that describes if for all ,
Let us use to denote this. We will use the size of the circuit to measure how complex the string is. Denote the size of the smallest circuit that describes as .
This is a natural generalization of the notion of sparse (we can also say succinct). Clearly, if a string is sparse, then there is a small circuit so that . More precisely,
Lemma: Suppose is a string of length with at most 1’s. Then, there is a circuit so that and the size of is . Thus,
For general circuits , this notion was addressed by Eric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, and Detlef Ronneburger in their paper Power from Random Strings, where they proved it polynomially equivalent to their modification of Leonid Levin’s variation of Kolmogorov’s original idea. See also this recent paper. However, we are interested when has additional properties, such as being a constant depth circuit of threshold gates.
Describing a Solution
Consider the linear system again,
where is an by invertible integer matrix and is an integer vector. The twist is that now we limit and to have description complexity of at most .
The key open question is simple: is there a solution to the linear equation so
This does not ask for an algorithm to find the solution , but asks how complex it is to describe a solution.
By Kolmogorov’s original notion, there is one solution that has a particularly short description. It is the unique in the solution space that minimizes the Euclidean distance to . The description of can take our size- circuit describing and , but then it appears we need to do iterative calculations to compute exactly or to a desired precision. The iterations are not so easy to describe—not by a constant-depth circuit. So can we describe this , or some other solution , another way?
The issue resembles that of computational depth. We have a very short description, but it is computationally substantial to “unpack,” hence deep. We want a description that is literally less deep to unpack. Where we are being “fair” is we only ask this for equations that are themselves not deep to specify. Those equations come from translating nondeterministic logspace Turing machines and their counting functions into linear algebra.
Describing an Approximate Solution
Consider the same linear system again. Given an can we describe a solution so that
I can weaken this question even further, but let’s leave that for another time.
If one can show that the last question can be answered in the affirmative, with variously restricted circuits describing the solution, then Ken Regan and I believe that we can prove new complexity class separation theorems. More on this in the future.
[fixed some typos]