Class Description

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.

Linked From

0-1-NPC: Binary Restriction of NP Over The Complex Numbers

The intersection of NPC with {0,1}* (i.e. the set of binary strings).

Contains NP.

Is contained in PSPACE, and in AM assuming the Extended Riemann Hypothesis [Koi96].

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...


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.

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...