This work is licensed under a
Creative Commons License.
|
Thursday, October 10, 2002
Complexity Class of the Week: PPrevious 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 n150 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
LD = { <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
LA = { <M> | Machine M does accept input <M>} LA is just LD.Note the LA is computably enumerable as we can just simulate M on <M>. If LA were computable then so would LD which we know is not even computably enumerable. Thus we have LA 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 SudanAvi 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 []