This work is licensed under a
Creative Commons License.
|
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=LPrevious 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
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).
- 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).
- 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).
- A probabilistic log-space machine M such that x is in L if and only if Pr(M(x) accepts) = 1/2.
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
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
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.
- {ε,0,1,001}
- The set of strings of odd length
- {1,10,110,1110,11110,...}
A class is a set of languages. Examples of classes include
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.
- 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}.
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).
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.
- M(x) outputs "yes" in which case we say M(x) accepts.
- M(x) outputs "no" in which case we say M(x) rejects.
- M(x) does not halt.
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 []