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

UAM^cc: Unambiguous Arthur-Merlin Communication Complexity

Similar to AM^cc except that for each yes-input and each outcome of Arthur’s (i.e., Alice's and Bob's) randomness, there must be a unique proof Merlin can send that will be accepted.

Does not contain NP^cc [GPW16a].

Is not contained in SBP^cc [GPW16a], [GLM+15].

Is contained in PostBPP^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.

---

UE: Unambiguous Exponential-Time With Linear Exponent

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

---

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].

---

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.

---

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.

---

UP^cc: Communication Complexity UP

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

The complexity measure corresponding to UP^cc 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:

• P^cc=UP^cc.
• The "Clique vs. Independent Set problem" CIS_G on a graph G (Alice gets a clique, Bob gets an independent set: do they intersect?) is "complete" for UP^cc in the sense that every f, say with UP^cc(f)=c, reduces to CIS_G for some G on 2^c many nodes.

The quadratic overhead in simulating UP^cc with P^cc, or equivalently the O(log²(n)) protocol for CIS_G, is known to be essentially optimal [GPW15].

---

UPostBPP^cc: Unrestricted Communication Analogue of PostBPP

Syntactically, this has the same relationship to PostBPP^cc as UPP^cc does to PP^cc; i.e., we only allow private (no public) randomness, and do not charge for α in the cost of a protocol.

Contains P^NPcc and hence does not equal PostBPP^cc since it has been shown that P^NPcc is not contained in PP^cc much less in PostBPP^cc [BVW07].

Contained in UPP^cc.

---

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 functions $f:\{0,1\}^{n}\times \{0,1\}^{n}\to \{0,1\}$ that are computable by polylogarithmic protocols using private (but no public) randomness, which 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.

Does not contain ⊕P^cc [For02].

Does not contain PH^cc [RS10].

The complexity measure associated with UPP^cc is equivalent to the log of the sign-rank of the communication matrix (assuming the latter has {1,-1} entries) [PS86].

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.

---

USBP^cc: Unrestricted Communication Analogue of SBP

Syntactically, this has the same relationship to SBP^cc as UPP^cc does to PP^cc; i.e., we only allow private (no public) randomness, and do not charge for α in the cost of a protocol. However, it has been shown that USBP^cc=SBP^cc [GLM+15].

---

UWAPP^cc: Unrestricted Communication Analogue of WAPP

Syntactically, this has the same relationship to WAPP^cc as UPP^cc does to PP^cc; i.e., we only allow private (no public) randomness, and do not charge for α in the cost of a protocol. However, it has been shown that UWAPP^cc protocols can be efficiently simulated by WAPP^cc protocols with a slightly larger ε parameter [GLM+15].