The class of decision problems solvable by an NP machine such that
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.
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].
The class of decision problems solvable by an NP machine such that
Contained in C=P, and in ModkP for any odd k. Contains UP.
Defined in [BHR00].
The class of decision problems solvable by an NP machine such that
Defined in [AR88].
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].
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.
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.
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 UP ∩ coUP, and a random oracle relative to which QSZK does not contain UP [MW18].
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.
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.
Has the same relation to E as UP does to P.
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].
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].
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.