### Thursday, October 10, 2002

**Complexity Class of the Week: P**

Previous CCW
Edmonds in his 1965 paper on
matching suggests defining efficient computation as those running in
time polynomial in the length of their input. This became the class P,
the most basic of all complexity classes.

The class P has nice properties, for example it is model independent,
i.e., P is the same whether one has a single-tape, multi-tape or
random-access Turing machine. P is closed under
subroutines--polynomial-time machines with access to an oracle for P
accept languages in P. Perhaps a running time like n^{150} is
not efficient but one needs the polynomial-time definition to keep the
robustness of the model. In nearly every case, natural problems shown
to be in P have also been shown to have algorithms with relatively low
exponents.

Some have argued that P as efficient computation reflects old
technology. Perhaps efficient computation should be classes like BPP
(probabilistic) or even BQP (quantum). I don't
know about you but the computer on my desk doesn't produce truly
random bits or quantum entanglement.

P is equal to alternating log-space. Using this result, we get
complete problems for P like the circuit value problem consisting of
the set of AND-OR circuits that evaluate to true. For P-completeness
we require the reductions to be computed in logarithmic space. P has
many other natural complete sets including variations on depth-first search.

There are many examples
of problems with nontrivial polynomial-time algorithms such as
matching, linear programming and primality.

Every language in P can be expressed as a first-order formula with
ordering and a least-fixed-point operator.

Many of the major open questions in complexity ask about the power of
P, for example P = BPP, P = BQP, P = PSPACE, P = L and of course P =
NP. Note that we cannot have both P = L and P = PSPACE since L =
PSPACE violates the space hierarchy.

10:00 AM
#
Comments
[]

### Wednesday, October 09, 2002

**Foundations of Complexity **

Lesson 4: Noncomputable Computably Enumerable Languages

Previous Lesson
| Next Lesson
In the last
lesson we showed that the set

L_{D} = { <M> | Machine M does not accept input <M>}
is not computably enumerable. In this lesson we show there are
languages that are computably enumerable but not computable.
For a set A, let A be
the complement of A, i.e., all of
the strings of Σ^{*} not in A. If A is computable then
A is also
computable--at the end if we accepted then we reject and
vice-versa.
Note this does not work in general for computably enumerable;
switching reject and accept does not affect whether a machine halts on
a given input.

Now consider the set

L_{A} = { <M> | Machine M does accept input <M>}
L_{A} is just
L_{D}.
Note the L_{A} *is* computably enumerable as we can just
simulate M on <M>. If L_{A} were computable then so would
L_{D} which we know is not even computably enumerable. Thus we
have L_{A} as our first example of a noncomputable computably
enumerable set.

Besides languages we can also consider computable functions. Consider
a Turing machine with an output tape. We can view it as computing a
function f from Σ^{*} to Σ^{*} where the
value of f is the contents of the output tape after the machine enters
a specified halting state. We say a total function f is computable if
there is such a Turing machine computing f. We can also consider
partially computable functions where f(x) may not be defined for some
inputs x. On these inputs the corresponding machine does not halt.

In the next lesson we will use computable functions to show that other
languages are not computable or computably enumerable.

4:02 PM
#
Comments
[]

### Monday, October 07, 2002

**Wigderson Paper on Work of Sudan**

Avi Wigderson has posted on his publications page an article about the research of Madhu Sudan, the recent Nevanlinna Prize recipient. The paper, written for a broad mathematical audience, gives a nice description of Madhu's work on probabilistically checkable proofs and error-correcting codes.
3:14 PM
#
Comments
[]