Class Description

PC: Polynomial-Time Over The Complex Numbers

An analog of P for Turing machines over a complex number field.

Defined in [BCS+97].

See also PR, NPC, NPR, VPk.

Linked From

NPC: NP Over The Complex Numbers

An analog of NP for Turing machines over a complex number field.

Defined in [BCS+97].

It is unknown whether PC = NPC, nor are implications known among this question, PR versus NPR, and P versus NP.

However, [CKK+95] show that if P/poly does not equal NP/poly then PC does not equal NPC.

[BCS+97] show the following striking result. For a positive integer n, let t(n) denote the minimum number of additions, subtractions, and multiplications needed to construct n, starting from 1. If for every sequence {nk} of positive integers, t(nk k!) grows faster than polylogarithmically in k, then PC does not equal NPC.

See also VNPk.

More about...


NPR: NP Over The Reals

An analog of NP for Turing machines over a real number field.

Defined in [BCS+97].

It is unknown whether PR = NPR, nor are implications known among this question, PC versus NPC, and P versus NP.

Also, in contrast to the case of NPC, it is an open problem to show that P/poly distinct from NP/poly implies PR distinct from NPR. The difference is that in the real case, a comparison (or greater-than) operator is available, and it is not known how much power this yields in comparison to the complex case.

See also VNPk.

More about...


P: Polynomial-Time

The class that started it all.

The class of decision problems solvable in polynomial time by a Turing machine. (See also FP, for function problems.)

Defined in [Edm65], [Cob64], [Rab60], and other seminal early papers.

Contains some highly nontrivial problems, including linear programming [Kha79] and finding a maximum matching in a general graph [Edm65].

Contains the problem of testing whether an integer is prime [AKS02], an important result that improved on a proof requiring an assumption of the generalized Riemann hypothesis [Mil76].

A decision problem is P-complete if it is in P, and if every problem in P can be reduced to it in L (logarithmic space). The canonical P-complete problem is circuit evaluation: given a Boolean circuit and an input, decide what the circuit outputs when given the input.

Important subclasses of P include L, NL, NC, and SC.

P is contained in NP, but whether they're equal seemed to be an open problem when I last checked.

Efforts to generalize P resulted in BPP and BQP.

The nonuniform version is P/poly, the monotone version is mP, and versions over the real and complex number fields are PR and PC respectively.

In descriptive complexity, P can be defined by three different kind of formulae, FO(lfp) which is also FO()], and also as SO(Horn)

P queries are exactly the one that can be written in the While/cons languages.

P is the class of decision problems solvable by a (logspace) uniform family of polynomial-size Boolean circuits.

P can be computed by interactive protocols (see IP) where the verifier runs in log space (see L and BPL) [GKR15].

More about...


PR: Polynomial-Time Over The Reals

An analog of P for Turing machines over a real number field.

Defined in [BCS+97].

See also PC, NPC, NPR, VPk.

More about...


VPk: Valiant P Over Field k

The class of efficiently-solvable problems in Valiant's algebraic complexity theory.

More formally, the input consists of constants c1,...,cm and indeterminates X1,...,Xn over a base field k (for instance, the complex numbers or Z2). The desired output is a collection of polynomials over the Xi's. The complexity is the minimum number of pairwise additions, subtractions, and multiplications needed by a straight-line program to produce these polynomials. VPk is the class of problems whose complexity is polynomial in n. (Hence, VPk is a nonuniform class, in contrast to PC and PR.)

Originated in [Val79b]; see [Bur00] for more information.

Contained in VNPk and VQPk, and contains VNCk.

More about...