Class Description

UP: Unambiguous Polynomial-Time

The class of decision problems solvable by an NP machine such that

  1. If the answer is 'yes,' exactly one computation path accepts.
  2. If the answer is 'no,' all computation paths reject.

Defined by [Val76].

"Worst-case" one-way functions exist if and only if P does not equal UP ([GS88] and independently [Ko85]). "Worst-case" one-way permutations exist if and only if P does not equal UP ∩ coUP [HT03]. Note that these are weaker than the one-way functions and permutations that are needed for cryptographic applications.

There exists an oracle relative to which P is strictly contained in UP is strictly contained in NP [Rac82]; indeed, these classes are distinct with probability 1 relative to a random oracle [Bei89].

NP is contained in RPPromiseUP [VV86]. On the other hand, [BBF98] give an oracle relative to which P = UP but still P does not equal NP.

UP is not known or believed to contain complete problems. [Sip82], [HH86] give oracles relative to which UP has no complete problems.

Linked From

coUP: Complement of UP

More about...


DisNP: Disjoint NP Pairs

The class of pairs (A,B), where A and B are NP problems whose sets of "yes" instances are nonempty and disjoint.

If there exists an optimal propositional proof system, then DisNP has a complete pair [Raz94]. On the other hand, there exists an oracle relative to which DisNP does not have a complete pair [GSS+03].

If P does not equal UP, then DisNP contains pairs not separated by any set in P [GS88]. On the other hand, there exists an oracle relative to which P does not equal NP but still DisNP does not contain any P-inseparable pairs [HS92].

More about...


EP: NP with 2k Accepting Paths

The class of decision problems solvable by an NP machine such that

  1. If the answer is 'no,' then all computation paths reject.
  2. If the answer is 'yes,' then the number of accepting paths is a power of two.

Contained in C=P, and in ModkP for any odd k. Contains UP.

Defined in [BHR00].

More about...


FewP: NP With Few Witnesses

The class of decision problems solvable by an NP machine such that

  1. If the answer is 'no,' then all computation paths reject.
  2. If the answer is 'yes,' then at least one path accepts; furthermore, the number of accepting paths is upper-bounded by a polynomial in n, the size of the input.

Defined in [AR88].

Is contained in ⊕P [CH89].

There exists an oracle relative to which P, UP, FewP, and NP are all distinct [Rub88].

Also, there exists an oracle relative to which FewP does not have a Turing-complete set [HJV93].

Contained in Few.

See also the survey [Tor90].

More about...


PermUP: Self-Permuting UP

The class of languages L in UP such that the mapping from an input x to the unique witness for x is a permutation of L.

Contains P.

Defined in [HT03], where it was also shown that the closure of PermUP under polynomial-time one-to-one reductions is UP.

On the other hand, they show that if PermUP = UP then E = UE.

See also: SelfNP.

More about...


PromiseUP: Promise-Problem UP

The class of promise problems solvable by an UP machine. I.e., the nondeterministic machine must have a unique accepting path for "yes" inputs, and no accepting paths "no" inputs, but could have any number of accepting paths for inputs that do not satisfy the promise.

Although not originally stated with this notation, the main result of [VV86] is that NP is contained in RPPromiseUP.

More about...


QSZK: Quantum Statistical Zero-Knowledge

A quantum analog of SZK (or more precisely HVSZK).

Arthur is a BQP (i.e. quantum) verifier who can exchange quantum messages with Merlin. So Arthur and Merlin's states may become entangled during the course of the protocol.

Arthur's "view" of his interaction with Merlin is taken to be the sequence of mixed states he has, over all steps of the protocol. The zero-knowledge requirement is that each of these states must have trace distance at most (say) 1/10 from a state that Arthur could prepare himself (in BQP), without help from Merlin. Arthur is assumed to be an honest verifier.

Defined in [Wat02], where the following was also shown:

Subsequently, [Wat09b] showed that honest-verifier and general-verifier quantum statistical zero-knowledge are equivalent.

There exists an oracle relative to which QSZK does not contain UPcoUP, and a random oracle relative to which QSZK does not contain UP [MW18].

More about...


span-P: Span Polynomial-Time

The class of functions computable as |S|, where S is the set of output values returned by the accepting paths of an NP machine.

Defined in [KST+89], where it is also shown that span-P contains #P and OptP; and that span-P = #P if and only if UP = NP.

More about...


UAP: Unambiguous Alternating Polynomial-Time

Same as AP, except we are promised that each existential quantifier has at most one 'yes' path, and each universal quantifier has at most one 'no' path.

Contains UP.

Defined in [NR98], where it was also shown that, even though AP = PSPACE, it is unlikely that the same is true for UAP, since UAP is contained in SPP.

[CGR+04] have also shown that UAPUAP = UAP, and that UAP contains Graph Isomorphism problem.

More about...


UE: Unambiguous Exponential-Time With Linear Exponent

Has the same relation to E as UP does to P.

More about...


UL: Unambiguous L

Has the same relation to L as UP does to P.

The problem of reachability in directed planar graphs lies in UL [SES05].

If UL = NL, then FNL is contained in #L [AJ93].

More about...


UPcc: Communication Complexity UP

Similar to NPcc except that the protocol is restricted to have exactly one accepting computation on each yes-input.

The complexity measure corresponding to UPcc is equivalent to the log of the number of rectangles needed to partition the set of 1-entries of the communication matrix.

Introduced in [Yan91], where it was shown that for total functions:

The quadratic overhead in simulating UPcc with Pcc, or equivalently the O(log2(n)) protocol for CISG, is known to be essentially optimal [GPW15].

More about...


US: Unique Polynomial-Time

The all-American counting class.

The class of decision problems solvable by an NP machine such that the answer is 'yes' if and only if exactly one computation path accepts.

In contrast to UP, a machine can legally have more than one accepting path - that just means that the corresponding input is not in the language.

Defined in [BG82].

Contains coNP.

More about...