Monday, September 30, 2002
A Reader's Question about Kolmogorov Complexity
Posted by Lance
My first question from a reader:
I'm interested in Kolmogorov complexity and its
relationship to traditional computational complexity
theory. It seems that
NPcomplete 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 NPcomplete sets, have low Kolmogorov complexity and are
not much use to measure the computational complexity of that
set. However, one can use timebounded Kolmogorov complexity to capture
computational complexity.
Let p be a tgood 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 ttimebounded instance complexity of an instance x of a set A as
ic^{t}(x:A) = min{p : p is a tgood 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.
4:49 PM
#
Posted by Lance
The New York Times has finally taken notice that there has been a surprisingly number of plays, movies and now an opera about science.
2:21 PM
#
0 comments
Saturday, September 28, 2002
Posted by Lance
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^{2}Dy^{2}=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 nbit 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 twoquery 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
quantph web site.
On quantph 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.
9:09 PM
#
Tuesday, September 24, 2002
Posted by Lance
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 onehalf.
11:23 PM
#
0 comments
Sunday, September 22, 2002
Posted by Lance
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.
6:13 AM
#
0 comments
Friday, September 20, 2002
Posted by Lance
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
#
0 comments
Posted by Lance
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
#
0 comments
Wednesday, September 18, 2002
Complexity Class of the Week: C_{=}L
Posted by Lance
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
#
0 comments
Monday, September 16, 2002
Foundations of Complexity
Lesson 2: Computable and Computably Enumerable Languages
Posted by Lance
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
#
0 comments
Friday, September 13, 2002
Complexity Class of the Week: Factoring
Posted by Lance
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
blackbox 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∩coNP: Guess the prime factorization of m. Since
every number has a unique prime factorization we have FACTOR in
UP∩coUP where UP is the set of languages accepted by NP machines
which have at most one accepting path for every input. The class
UP∩coUP 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∩coUP 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∩coUP.
8:33 AM
#
0 comments
Thursday, September 12, 2002
Posted by Lance
Who says you can't make money with mathematics? Here is an interesting Wired article on the MIT Blackjack team.
12:53 PM
#
0 comments
Science Screenplay Contest
Posted by Lance
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.
5:49 AM
#
0 comments
Wednesday, September 11, 2002
Posted by Lance
On September 11, 2001 we lost a member of the theoretical computer science community. Danny Lewin,
an MIT graduate student who
went on to cofound 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.
6:14 AM
#
0 comments
Sunday, September 08, 2002
Foundations of Complexity
Lesson 1: What is a computer?
Posted by Lance
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 ChurchTuring 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 ChurchTuring 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.
7:25 PM
#
2 comments
Thursday, September 05, 2002
Posted by Lance
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 coRP 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: (ImpagliazzoKabanets)
At least one of the following must be true
 PI requires deterministic exponential time to solve.
 The permanent does not have polynomialsize arithmetic circuits.
 NEXP does not have polynomialsize 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
selfreduction 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 polynomialsize 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
#Pcomplete.
Now suppose NEXP has polynomialsize circuits. By
ImpagliazzoKabanetsWigderson 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.
5:12 AM
#
0 comments
Wednesday, September 04, 2002
Complexity Class of the Week: PP
Posted by Lance
Previous CCW
A language L is in PP if there
is a nondeterministic polynomialtime 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 Polynomialtime" from the original definition by
Gill where one uses a probabilistic polytime TM where x is in L
if and only if the probability of M(x) accepting is greater than
1/2. "Probabilistic PolynomialTime" would be a better name for PP's
cousin class BPP or "Boundederror Probabilistic PolynomialTime".
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 MajorityP 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 polynomialtime
hierarchy to P^{PP}.
Valiant's proof that the permanent is #Pcomplete 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 coNP 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 truthtable 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 allpurpose
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 highdegree or very large
coefficients.
PP has interesting relationships to other complexity
classes. Vereshchagin
shows that MerlinArthur 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 uniformTC^{0}, constantdepth
circuits with threshold gates. Can one show that PP is not equal to
logspace? All one has to do is show that Toda's theorem can
be extended to get any nonconstant level of the polynomialtime
hierarchy to fall in P^{PP}.
7:40 AM
#
0 comments
Tuesday, September 03, 2002
Posted by Lance
Today's New York Times has an essay on primes and the new AKS algorithm. A bit rambling but worth a look.
5:30 AM
#
0 comments
Monday, September 02, 2002
Posted by Lance
Today is a major holiday in the US, Labor Day. The holiday's original meaning has been mostly lostit 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.
9:06 AM
#
0 comments