Complexity Zoo:U

Back to the Main Zoo - Complexity Garden - Zoo Glossary - Zoo References

---

Complexity classes by letter: Symbols - A - B - C - D - E - F - G - H - I - J - K - L - M - N - O - P - Q - R - S - T - U - V - W - X - Y - Z

Lists of related classes: Communication Complexity - Hierarchies - Nonuniform

---

UAM^cc - UAP - UCC - UCFL - UE - UL - UL/poly - UP - UP^cc - UPostBPP^cc - UPP^cc - US - USBP^cc - UWAPP^cc

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 UAP^UAP = UAP, and that UAP contains Graph Isomorphism problem.

---

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.

Equals L. [Rei04]

The corresponding class for directed graphs equals NL. On the other hand, none of that class's corresponding search problems are obviously FNL-hard.

---

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.

Strictly contains Deterministic CFL. Strictly contained in CFL.

---

UL: Unambiguous L

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

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

---

UL/poly: Nonuniform UL

Has the same relation to UL as P/poly does to P.

Equals NL/poly [RA00]. (A corollary is that UL/poly is closed under complement).

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

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

---

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 RP^PromiseUP [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.

---

UPP^cc: Unrestricted Communication Analogue of PP

Defined by [BFS86], UPP^cc is one of two communication complexity analogues of PP. UPP^cc is the class of all languages defined by functions $f:\{0,1\}^{n}\times \{0,1\}^{n}\to \{0,1\}$ which are computable by polylogarithmic protocols that accept with probability strictly greater than 1/2 when $f(x,y)=1$ 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: PP^cc.

---

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.