Computational Complexity

Thursday, October 10, 2002

 
Complexity Class of the Week: P

Posted by Lance

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¹⁵⁰ 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 # 0 comments

Comment Feeds: This Post All