Computational Complexity


Creative Commons License
This work is licensed under a Creative Commons License.

Powered by Blogger™

Friday, September 20, 2002

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.

3:48 PM # Comments []  

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(n12) 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 n12 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.

10:13 AM # Comments []  

Wednesday, September 18, 2002

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.

4:25 PM # Comments []  

Monday, September 16, 2002

Foundations of Complexity
Lesson 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.

6:20 AM # Comments []