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.
UCC: Unique Connected Component
The class of problems reducible in L to the problem of whether an undirected graph has a unique connected component.
See [AG00] for more information.
UCFL: Unambiguous CFL
The class of context-free languages which can be represented by grammars where each word in the language has exactly one leftmost derivation.
UL: Unambiguous L
UL/poly: Nonuniform UL
Note that in UL/poly, the witness must be unique even for bad advice. UL/mpoly (as in BQP/mpoly) is a more natural definition, but this is a moot distinction here because [RA00] show that they both equal NL/poly.
UE: Unambiguous Exponential-Time With Linear Exponent
UP: Unambiguous Polynomial-Time
The class of decision problems solvable by an NP machine such that
- If the answer is 'yes,' exactly one computation path accepts.
- 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.
UPPcc: Unrestricted Communication Analogue of PP
Defined by [BFS86], UPPcc is one of two communication complexity analogues of PP. UPPcc is the class of all languages defined by functions which are computable by polylogarithmic protocols that accept with probability strictly greater than 1/2 when and accept with probably strictly less than 1/2 otherwise. No accounting is made for how many random bits are consulted during the protocol.
See also: PPcc.
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].