A Reader's Question about Kolmogorov Complexity

My first question from a reader:

I'm interested in Kolmogorov complexity and its relationship to traditional computational complexity theory. It seems that NP-complete problems all have a pretty low Kolmogorov complexity, so in this sense it seems KC will not serve as a good measure for problem instance hardness. I would like to know what you would say on this topic sometime in the future.

Andrei Nikolaevich Kolmogorov was born on April 25, 1903 and in 2003 there will be several events to mark the 100th anniversary of his birth. I plan to devote several posts next year to mark these events and discuss Kolmogorov complexity. If you cannot wait, I recommend the great textbook on the topic, An Introduction to Kolmogorov Complexity and Its Applications by Ming Li and Paul Vitányi.

As to the reader's question, initial segments of any computable set, including the NP-complete sets, have low Kolmogorov complexity and are not much use to measure the computational complexity of that set. However, one can use time-bounded Kolmogorov complexity to capture computational complexity.

Let p be a t-good program for a set A if for all inputs x, p(x) uses t(|x|) time and says "Yes", "No" or "I don't know". If p(x) says Yes then x is in A and if p(x) says "No" then x is not in A.

We define the t-time-bounded instance complexity of an instance x of a set A as

ic^t(x:A) = min{|p| : p is a t-good program for A and p(x) ≠ "I don't know"}

We have that A is in P if and only if there is a constant c and a polynomial q such that for all x, ic^q(x:A)≤ c. To prove P ≠ NP one only needs to that ic^q(x:SAT) is unbounded for all polynomials q.

For more information about instance complexity see Section 7.4 of Li and Vitányi.

The New York Times has finally taken notice that there has been a surprisingly number of plays, movies and now an opera about science.

The Quantum Algorithms and Complexity workshop clearly showed a field matured. From at least a computer science point of view, researchers have created a strong set of techniques and questions that are leading to several new and exciting results. Let me give you an example of some of the results presented at the workshop.

There were new quantum algorithms. Sean Halgreen showed how to solve Pell equations, i.e. given x and y, find a value D such that x²-Dy²=1. Wim van Dam showed how to estimate Gauss sums, which I won't define.

Some new and interesting limitations on quantum computing. Ambainis presented Razborov's newest result giving a n^0.5 lower bound on the communication complexity of set disjointness: Given two parties with two n-bit strings, they need to transmit even n^0.5 quantum bits to determine if there is an i such that both strings have a 1 in the ith bit.

The most fascinating result was due to Ronald de Wolf who gave lower bounds on two-query locally decodable codes in the classical model using quantum techniques. He first showed how to simulate two classical queries with one quantum query and then gave a lower bound on the one quantum query model.

If you would like to learn more about quantum computing I suggest the textbook, Quantum Computation and Quantum Information by Nielsen and Chuang. Nearly all quantum computation papers can be found at the quant-ph web site.

On quant-ph you can find David Mermin's From Cbits to Qbits: Teaching computer scientists quantum mechanics which I mention just because I am the "newly enlightened computer scientist" quoted on the first page. Feel free to read my paper One complexity theorist's view of quantum computing based on my AQIP talk for another point of view.

Howdy from Canada. I have limited internet access here in Banff so there won't be many posts this week.

I've heard lots of interesting results about quantum computing here. John Watrous has the following nifty theorem about quantum interactive proofs:
Every language with a quantum interactive proof (and in particular all of PSPACE) has a proof system that works as follows: Merlin sends some qbits to Arthur. Arthur flips a single classical coin and sends it to Merlin. Merlin then sends over more qbits and Arthur performs some quantum operations and accepts or rejects. Even though Arthur's only communication is a single random coin, this protocol has perfect completeness and soundness near one-half.

I'm off to beautiful Banff, Canada for the MSRI Workshop on Quantum Algorithms and Complexity. So no regular features this week but I hope to bring you the latest in quantum computation.

Ketan Mulmuley and Milind Sohoni have an interesting approach to separating complexity classes using algebraic geometry. Ken Regan describes this approach for the common complexity theorist in the October BEATCS Computational Complexity Column.

I saw Carl Pomerance yesterday give a wonderful presentation on the AKS primality algorithm. He made an interesting point about the algorithm. The algorithm runs in time O(n¹²) where n is the number of bits of the input to be tested. The big O notation hides a constant, i.e., the algorithm uses c n¹² for some constant c. That c is unknown!

The AKS algorithm uses a result by Fouvry on the distribution of certain kinds of primes. Fouvry's result uses another result that is proven as such: First it is proved assuming the Extended Riemann Hypothesis is true. If the ERH fails, then the place where it fails can be used to prove the result. The constant c will depend on where the ERH fails. To determine c would require settling the Extended Riemann Hypothesis!

Agrawal, Saxena and Kayal did not cheat; they really gave a polynomial-time algorithm for primality. Their algorithm is fixed, only the analysis of the running time is affected by the ERH. Also there are other results one can use instead of Fouvry that get around this issue. Still I find it neat that this algorithm that gives a provably polynomial-time algorithm for primality has a running time that, while polynomial, is completely unknown.

Complexity Class of the Week: C=L

Previous CCW

Sometimes a class that seems a mix of concepts turns out to have significant meaning. C₌L is one of these classes. First we need to define the class.

Consider a nondeterministic log-space Turing machine M that never repeats a configuration. This is not much of a restriction since we can just add a clock to the machine. Let #L be the set of functions such that f(x) is the number of accepting paths of M(x) for some M as described above. Let GapL be the closure of #L under subtraction.

We say a language L is in C₌L if there exists
a function f in GapL such that for all x, x is in L if and only if f(x)=0. (*)

C₌L is the log-space equivalent of the counting class C₌P. There are many equivalent definitions to C₌L where we can replace (*) by

1. A function f in GapL and a function log-space computable function g such that for all x, x is in L if and only if f(x)=g(x).
2. A function f in #L and a log-space computable function g such that for all x, x is in L if and only if f(x)=g(x).
3. A probabilistic log-space machine M such that x is in L if and only if Pr(M(x) accepts) = 1/2.

The neat part of C₌L is that it has a nice complete problem: singular integer matrices. This is because for every GapL function f there is a log-space computable g mapping strings to integer matrices such that f(x) is the determinant of g(x).

The big open question about C₌L is whether it is closed under complement, i.e., is there a log-space computable function g mapping matrices to matrices such that M is singular if and only if g(M) is nonsingular?

For more information about C₌L and related classes including references and proofs of the above see the paper of Eric Allender and Mitsu Ogihara, Relationships among PL, #L, and the Determinant, RAIRO - Theoretical Informatics and Applications Vol. 30, 1996, pp. 1-21.

Foundations of ComplexityLesson 2: Computable and Computably Enumerable Languages

Previous Lesson | Next Lesson

In Lesson 1 we described the Turing machine model to answer the question, "What is a computer?" The next question is "What can we compute?" First we need some definitions to describe problems to be computed.

First we need an alphabet which we denote Σ. Any finite Σ would work; for most of complexity we assume that Σ = {0,1}. Machines take as inputs words or strings consisting of a finite sequence of alphabet symbols or characters. Examples: 0101, 000, 1101100. The length of the string is the number of characters in the string. We use ε to represent the special string with zero characters.

A language is set of strings. It could be finite or infinite. Examples include

• {ε,0,1,001}
• The set of strings of odd length
• {1,10,110,1110,11110,...}

We use Σ^* to represent the set of all strings and ∅ to represent the empty set of no elements. Note the difference between the empty set of strings and {ε}, the set consisting of the single string of length zero.

A class is a set of languages. Examples of classes include

• The class of all finite languages.
• The class of all languages containing the string ε.
• The class of all languages that are subsets of {0,1,00,11,101}.

A complexity class is a special kind of class based on resource-bounded Turing machines. We will come back to complexity classes in a later lesson.

Consider a Turing machine M on some input string x which we denote M(x). We will focus on two possible outputs "yes" or "no". This yields three possibilities for M(x).

1. M(x) outputs "yes" in which case we say M(x) accepts.
2. M(x) outputs "no" in which case we say M(x) rejects.
3. M(x) does not halt.

We let L(M) be the set of strings x such that the first case occurs. A machine M such that the third case does not occur for any x is called total.

The class of computably enumerable languages is the set of languages L such that L = L(M) for some Turing machine M. You might see recognizable or recursively enumerable as other names for the computably enumerable languages.

The class of computable languages consists of the set of languages L such that L = L(M) for some total Turing machine M. You might see decidable or recursive as other names for the computable languages.

Complexity Class of the Week: Factoring

Previous CCW

Factoring is not a class, it is not even a language. Nevertheless it has some interesting connections to complexity classes that are worth discussing.

Factoring is the problem of taking a number m and producing the prime factors of m. There are a number of algorithms for factoring but they all take time exponential in the length of the input (log m) in the worst case. Here is a good place to start reading about these algorithms.

Factoring gives a great example of an issue that often arises in complexity, search versus decision. It has always amazed me that we can easily determine whether a number has nontrivial factors but finding these factors is apparently much more difficult. This distinction and some other nice properties of numbers makes factoring very useful in cryptography.

To consider the computational complexity of factoring, we need to make a language version.

FACTOR = {(m,r) | There is an s, 1<s<r such that s divides m}
FACTOR is computationally equivalent to factoring: (m,r) is in FACTOR if and only if r is greater than the least prime factor of m. Given a black-box for FACTOR one can use binary search to find a prime factor of m.

If one insists on a complexity class, one could consider all the languages reducible to FACTOR but there is not much value beyond considering the complexity of the language FACTOR.

FACTOR is in NP∩co-NP: Guess the prime factorization of m. Since every number has a unique prime factorization we have FACTOR in UP∩co-UP where UP is the set of languages accepted by NP machines which have at most one accepting path for every input. The class UP∩co-UP is arguably the smallest interesting complexity class not known to have efficient algorithms and, assuming factoring is hard, really does not have efficient algorithms. I should note that FACTOR in UP∩co-UP was known before the recent AKS primality algorithm but the proof was more difficult.

Peter Shor almost singlehandedly justified the study of quantum computing by his efficient quantum algorithm for factoring, in complexity terms FACTOR in BQP. His proof used the fact that factoring of a number m can be reduced to finding the order of the multiplicative group (mod n). Shor then shows that quantum computers can solve this kind of group question.

Factoring does not appear to be hard for any nontrivial complexity class. This means that unlike Satisfiability we don't have any reason to believe that factoring is hard other than the fact that many smart people have failed to solve it. On the other hand the hardness of factoring is taken as a given in the study of complexity and cryptography and used to show the hardness of classes like UP∩co-UP.

Who says you can't make money with mathematics? Here is an interesting Wired article on the MIT Blackjack team.

Science Screenplay Contest

Have you secretly been writing a movie script about a computer scientist? Now is your chance. Robert De Niro's Tribeca Film Institute in conjunction with the Sloan foundation is looking for movie scripts with a lead character who is a scientist, mathematician or engineer. No science fiction stories will be accepted.

Update 8/4/05: See the winners.

On September 11, 2001 we lost a member of the theoretical computer science community. Danny Lewin, an MIT graduate student who went on to co-found Akamai was on board the American Airlines flight that crashed in New York City. He and the other victims of that day will always be remembered.

Foundations of Complexity Lesson 1: What is a computer?

Next Lesson

This is the first of a long series of posts giving an informal introduction to computational complexity.

Computational complexity theorists try to determine which problem are efficiently solvable on a computer. This sentence already leads to many questions: What is a problem? What is efficiently solvable? Let us first start off with a truly basic question, what is a computer?

In 1936, Alan Turing invented a theoretical computing device now called a Turing Machine. This was before electronic computers existed. He tried to give a simple model of the thought processes of mathematicians. His model has stood the test of time and represents the official model of computation that we still study today.

Instead of giving the formal definition of a Turing machine, let us try a more modern approach. Consider some current programming language like Java. Let us consider the (imaginary) world where a Java program has access to a potentially infinite amount of storage. A Turing machine corresponds to a specific Java program. You might find it a little confusing to think of Turing machine = Java Program but that is the best way to think about it.

Does it matter which programming language we choose? What if we used C++ or Visual Basic or the original Turing machine model? No, it makes no difference. Consider a C++ program P. There are, at least theoretically, Java programs that will interpret C++ programs. If you consider a Java program that interprets P, it will have the same computational behavior as P. This idea holds between any two programming languages including the original Turing machine and leads to the Church-Turing thesis:

Everything computable is computable by a Turing machine.
Which you can interpret as saying everything is computable is computable by a Java program.

The Church-Turing thesis cannot be proven as it is a thesis but has lead us to define computable as computable by a Turing machine. Now after about half a century of having real computers, the Turing machine has really proven itself as the right model of computation.

I heard of a nice new result from Russell Impagliazzo and Valentine Kabanets yesterday. Consider the language PI (Polynomial Identities) consisting of multivariate polynomials which are identically zero. PI is in co-RP by replacing the variables by random values and seeing if the result is zero. There is a lemma by Schwartz that implies this randomized algorithm will work with high confidence.

Since we now know Primality is in P, PI is the best remaining example of a problem with an efficient probabilistic algorithm but no known deterministic algorithm. Unlike primality, giving even a weak derandomization for PI will be difficult as it will lead to circuit lower bounds.

Theorem: (Impagliazzo-Kabanets) At least one of the following must be true

1. PI requires deterministic exponential time to solve.
2. The permanent does not have polynomial-size arithmetic circuits.
3. NEXP does not have polynomial-size Boolean circuits.

Here is a sketch of the proof. For a matrix A let A_ij represent A with the ith row and jth column removed. Consider the self-reduction from the permanent of a (k+1)×(k+1) matrix to permanents of k×k matrices
(*) Perm(A) = Σ_j a_1j Perm(A_1j)

Suppose that the permanent has polynomial-size arithmetic circuits. Then P^#P is computable in NP^PI by the following algorithm: Guess the arithmetic circuits for the Permanent for all sizes k×k up to n×n for some appropriate n. Use PI to verify (*) for each k<n. If the test is correct on all lengths than the circuits are correct. Use the circuits to compute the Permanent which is #P-complete.

Now suppose NEXP has polynomial-size circuits. By Impagliazzo-Kabanets-Wigderson this implies NEXP = MA ⊆ PH ⊆ P^#P ⊆ NP^PI. If PI is computable in subexponential time then NEXP is in nondeterministic subexponential time, contradicting the nondeterministic time hierarchy.

Complexity Class of the Week: PP

Previous CCW

A language L is in PP if there is a nondeterministic polynomial-time Turing machine M such that x is in L if and only if M(x) has more accepting than rejecting paths.

PP stands for "Probabilistic Polynomial-time" from the original definition by Gill where one uses a probabilistic poly-time TM where x is in L if and only if the probability of M(x) accepting is greater than 1/2. "Probabilistic Polynomial-Time" would be a better name for PP's cousin class BPP or "Bounded-error Probabilistic Polynomial-Time". PP is not much use as a probabilistic class since it would take potentially an exponential number of trials to distinguish accepting from rejecting with reasonable confidence

A better name for PP would be Majority-P as given by the definition above. Because of historic reasons we are stuck with the name PP for now. Don't hold the bad name against the class. It still has a natural definition and some amazing properties.

PP has similar complexity to the function class #P as P^PP = P^#P, proved using the old stalwart, binary search. I have never found the paper that first proves this equivalence. Toda's Theorem shows the amazing hardness of PP by reducing the polynomial-time hierarchy to P^PP.

Valiant's proof that the permanent is #P-complete also gives a natural complete language for PP:

PERM = { (M,k) | The permanent of M is at least k}

NP is in PP by adding a larger number of dummy accepting paths. PP is clearly closed under complement so we have co-NP in PP. Beigel, Reingold and Spielman show that PP is closed under union, a far trickier proof than one would expect using the fact that rational functions approximate the sign function well. Fortnow and Reingold build on their techniques to show that PP is closed under truth-table reductions.

PP is the prototypical counting class, classes defined in terms of the number of accepting and rejecting paths. PP contains the counting class C₌P where x is in the language if the number of accepting paths equals the number of rejecting paths. On the other hand there are relativized worlds where ⊕P and PP are incomparable.

The limitations of PP come from what I call the Beigel all-purpose oracle. Beigel exhibits a relativized world where P^NP is not contained in PP. His proof works by showing that any polynomial whose sign is the ODDMAXBIT function must either have high-degree or very large coefficients.

PP has interesting relationships to other complexity classes. Vereshchagin shows that Merlin-Arthur games, the class MA, is contained in PP but gives a relativized world where AM is not in PP. Adleman, DeMarrais and Huang show that the quantum class BQP is contained in PP. Watrous shows that QMA, the quantum version of MA, is also contained in PP.

Fortnow and Rogers, building Lide Li's Ph.D. thesis, show that BQP is low for PP, i.e., PP^BQP = PP. Köbler, Schöning and Torán also using the work of Li show that graph isomorphism is also low for PP.

Allender shows that PP is not equal to uniform-TC⁰, constant-depth circuits with threshold gates. Can one show that PP is not equal to log-space? All one has to do is show that Toda's theorem can be extended to get any nonconstant level of the polynomial-time hierarchy to fall in P^PP.

Today's New York Times has an essay on primes and the new AKS algorithm. A bit rambling but worth a look.

Today is a major holiday in the US, Labor Day. The holiday's original meaning has been mostly lost-it now represents the unofficial end of summer. Welcome Fall.

Because of the holiday there is not much of a post today. Just let me point to the accepted papers of the FST&TCS Conference. FST&TCS is the main Indian theory conference.

Back on Wednesday with the next Complexity Class of the Week.