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(n^{12}) 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^{12} 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
polynomialtime 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 polynomialtime 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 logspace 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 logspace equivalent of the
counting class C_{=}P. There are many equivalent definitions
to C_{=}L where we can replace (*) by

A function f in GapL and a function logspace 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 logspace computable function g such
that for all x, x is in L if and only if f(x)=g(x).
 A
probabilistic logspace 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 logspace 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 logspace 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. 121.
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 resourcebounded 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).
 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.
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
[]