Class Description

P^||NP: P With Parallel Queries To NP

Equals P^NP[log] ([BH91] and [Hem89] independently).

Linked From

EXP: Exponential Time

Equals the union of DTIME(2^p(n)) over all polynomials p.

Also equals P with E oracle.

If L = P then PSPACE = EXP.

If EXP is in P/poly then EXP = MA [BFL91].

Problems complete for EXP under many-one reductions have measure 0 in EXP [May94], [JL95].

There exist oracles relative to which

• EXP = NP = ZPP [Hel84a], [Hel84b], [Hel86],
• EXP = NEXP but still P does not equal NP [Dek76],
• EXP does not equal PSPACE [Dek76].

[BT04] show the following rather striking result: let A be many-one complete for EXP, and let S be any set in P of subexponential density. Then A-S is Turing-complete for EXP.

[SM03] show that if EXP has circuits of polynomial size, then P can be simulated in MA_POLYLOG such that no deterministic polynomial-time adversary can generate a list of inputs for a P problem that includes one which fails to be simulated. As a result, EXP ⊆ MA if EXP has circuits of polynomial size.

[SU05] show that EXP ${\displaystyle \not \subseteq }$ NP/poly implies EXP ${\displaystyle \not \subseteq }$ P^||NP/poly.

In descriptive complexity EXPTIME can be defined as SO(${\displaystyle 2^{n^{O(1)}}}$) which is also SO(LFP)

More about...

NP/log: NP With Logarithmic Advice

Same as NP/poly, except that now the advice string is logarithmic-size.

Shown in [FK05] that EXP ⊆ NP/log if and only if EXP = P^||NP.

More about...

P^NP[log]: P With Log NP Queries

Also known as Θ₂^P.

The class of decision problems solvable by a P machine, that can make O(log n) queries to an NP oracle (where n is the length of the input).

Equals P^||NP, the class of decision problems solvable by a P machine that can make polynomially many nonadaptive queries to an NP oracle (i.e. queries that do not depend on the outcomes of previous queries) ([BH91] and [Hem89] independently).

P^NP[log] is contained in PP [BHW89].

Determining the winner in an election system proposed in 1876 by Charles Dodgson (a.k.a. Lewis Carroll) has been shown to be complete for P^NP[log] [HHR97].

Contains P^NP[k] for all constants k.

More about...