# Difference between revisions of "Complexity Zoo:U"

m (1 revision: Complexity zoo import.) |
|||

(20 intermediate revisions by 2 users not shown) | |||

Line 2: | Line 2: | ||

{{CZ-Letter-Menu|U}} | {{CZ-Letter-Menu|U}} | ||

+ | |||

+ | ===== <span id="uamcc" style="color:red">UAM<sup>cc</sup></span>: Unambiguous Arthur-Merlin Communication Complexity ===== | ||

+ | |||

+ | Similar to [[Complexity Zoo:A#amcc|AM<sup>cc</sup>]] 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 [[Complexity Zoo:N#npcc|NP<sup>cc</sup>]] [[zooref#gpw16a|[GPW16a]]]. | ||

+ | |||

+ | Is not contained in [[Complexity Zoo:S#sbpcc|SBP<sup>cc</sup>]] [[zooref#gpw16a|[GPW16a]]], [[zooref#glm+15|[GLM+15]]]. | ||

+ | |||

+ | Is contained in [[Complexity Zoo:P#postbppcc|PostBPP<sup>cc</sup>]]. | ||

+ | |||

+ | ---- | ||

===== <span id="uap" style="color:red">UAP</span>: Unambiguous Alternating Polynomial-Time ===== | ===== <span id="uap" style="color:red">UAP</span>: Unambiguous Alternating Polynomial-Time ===== | ||

Line 19: | Line 31: | ||

See [[zooref#ag00|[AG00]]] for more information. | See [[zooref#ag00|[AG00]]] for more information. | ||

− | + | Equals [[Complexity Zoo:L#l|L]]. [[zooref#rei00|[Rei04]]] | |

− | + | The corresponding class for directed graphs equals [[Complexity Zoo:N#nl|NL]]. On the other hand, none of that class's corresponding search problems are obviously [[Complexity Zoo:F#fnl|FNL]]-hard. | |

---- | ---- | ||

Line 30: | Line 42: | ||

Strictly contains [[Complexity Zoo:D#dcfl|Deterministic CFL]]. Strictly contained in [[Complexity Zoo:C#cfl|CFL]]. | Strictly contains [[Complexity Zoo:D#dcfl|Deterministic CFL]]. Strictly contained in [[Complexity Zoo:C#cfl|CFL]]. | ||

+ | |||

+ | ---- | ||

+ | ===== <span id="ue" style="color:red">UE</span>: Unambiguous Exponential-Time With Linear Exponent ===== | ||

+ | Has the same relation to [[Complexity Zoo:E#e|E]] as [[#up|UP]] does to [[Complexity Zoo:P#p|P]]. | ||

---- | ---- | ||

Line 35: | Line 51: | ||

===== <span id="ul" style="color:red">UL</span>: Unambiguous [[Complexity Zoo:L#l|L]] ===== | ===== <span id="ul" style="color:red">UL</span>: Unambiguous [[Complexity Zoo:L#l|L]] ===== | ||

Has the same relation to [[Complexity Zoo:L#l|L]] as [[#up|UP]] does to [[Complexity Zoo:P#p|P]]. | Has the same relation to [[Complexity Zoo:L#l|L]] as [[#up|UP]] does to [[Complexity Zoo:P#p|P]]. | ||

+ | |||

+ | The problem of reachability in directed <i>planar</i> graphs lies in UL [[zooref#ses05|[SES05]]]. | ||

If UL = [[Complexity Zoo:N#nl|NL]], then [[Complexity Zoo:F#fnl|FNL]] is contained in [[Complexity Zoo:Symbols#sharpl|#L]] [[zooref#aj93|[AJ93]]]. | If UL = [[Complexity Zoo:N#nl|NL]], then [[Complexity Zoo:F#fnl|FNL]] is contained in [[Complexity Zoo:Symbols#sharpl|#L]] [[zooref#aj93|[AJ93]]]. | ||

---- | ---- | ||

+ | |||

===== <span id="ulpoly" style="color:red">UL/poly</span>: Nonuniform [[#ul|UL]] ===== | ===== <span id="ulpoly" style="color:red">UL/poly</span>: Nonuniform [[#ul|UL]] ===== | ||

Has the same relation to [[#ul|UL]] as [[Complexity Zoo:P#ppoly|P/poly]] does to [[Complexity Zoo:P#p|P]]. | Has the same relation to [[#ul|UL]] as [[Complexity Zoo:P#ppoly|P/poly]] does to [[Complexity Zoo:P#p|P]]. | ||

Line 45: | Line 64: | ||

Note that in UL/poly, the witness must be unique even for bad advice. UL/mpoly (as in [[Complexity Zoo:B#bqpmpoly|BQP/mpoly]]) is a more natural definition, but this is a moot distinction here because [[zooref#ra00|[RA00]]] show that they both equal [[Complexity Zoo:N#nlpoly|NL/poly]]. | Note that in UL/poly, the witness must be unique even for bad advice. UL/mpoly (as in [[Complexity Zoo:B#bqpmpoly|BQP/mpoly]]) is a more natural definition, but this is a moot distinction here because [[zooref#ra00|[RA00]]] show that they both equal [[Complexity Zoo:N#nlpoly|NL/poly]]. | ||

− | |||

− | |||

− | |||

− | |||

---- | ---- | ||

Line 66: | Line 81: | ||

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

+ | |||

+ | ---- | ||

+ | |||

+ | ===== <span id="upcc" style="color:red">UP<sup>cc</sup></span>: Communication Complexity [[Complexity Zoo:U#up|UP]] ===== | ||

+ | |||

+ | Similar to [[Complexity Zoo:N#npcc|NP<sup>cc</sup>]] except that the protocol is restricted to have exactly one accepting computation on each yes-input. | ||

+ | |||

+ | The complexity measure corresponding to UP<sup>cc</sup> is equivalent to the log of the number of rectangles needed to partition the set of 1-entries of the communication matrix. | ||

+ | |||

+ | Introduced in [[zooref#yan91|[Yan91]]], where it was shown that for total functions: | ||

+ | <ul> | ||

+ | <li> [[Complexity Zoo:P#pcc|P<sup>cc</sup>]]=UP<sup>cc</sup>. | ||

+ | <li> The "Clique vs. Independent Set problem" CIS<sub>G</sub> on a graph G (Alice gets a clique, Bob gets an independent set: do they intersect?) is "complete" for UP<sup>cc</sup> in the sense that every f, say with UP<sup>cc</sup>(f)=c, reduces to CIS<sub>G</sub> for some G on 2<sup>c</sup> many nodes. | ||

+ | </ul> | ||

+ | |||

+ | The quadratic overhead in simulating UP<sup>cc</sup> with [[Complexity Zoo:P#pcc|P<sup>cc</sup>]], or equivalently the O(log<sup>2</sup>(n)) protocol for CIS<sub>G</sub>, is known to be essentially optimal [[zooref#gpw15|[GPW15]]]. | ||

+ | |||

+ | ---- | ||

+ | |||

+ | ===== <span id="upostbppcc" style="color:red">UPostBPP<sup>cc</sup></span>: Unrestricted Communication Analogue of [[#postbpp|PostBPP]] ===== | ||

+ | |||

+ | Syntactically, this has the same relationship to [[Complexity Zoo:P#postbppcc|PostBPP<sup>cc</sup>]] as [[Complexity Zoo:U#uppcc|UPP<sup>cc</sup>]] does to [[Complexity Zoo:P#ppcc|PP<sup>cc</sup>]]; i.e., we only allow private (no public) randomness, and do not charge for α in the cost of a protocol. | ||

+ | |||

+ | Contains [[Complexity Zoo:P#pnpcc|P<sup>NPcc</sup>]] and hence does not equal [[Complexity Zoo:P#postbppcc|PostBPP<sup>cc</sup>]] since it has been shown that [[Complexity Zoo:P#pnpcc|P<sup>NPcc</sup>]] is not contained in [[Complexity Zoo:P#ppcc|PP<sup>cc</sup>]] much less in [[Complexity Zoo:P#postbppcc|PostBPP<sup>cc</sup>]] [[zooref#bvw07|[BVW07]]]. | ||

+ | |||

+ | Contained in [[Complexity Zoo:U#uppcc|UPP<sup>cc</sup>]]. | ||

---- | ---- | ||

Line 71: | Line 112: | ||

===== <span id="uppcc" style="color:red">UPP<sup>cc</sup></span>: Unrestricted Communication Analogue of [[Complexity Zoo:P#pp|PP]] ===== | ===== <span id="uppcc" style="color:red">UPP<sup>cc</sup></span>: Unrestricted Communication Analogue of [[Complexity Zoo:P#pp|PP]] ===== | ||

Defined by [[zooref#bfs86|[BFS86]]], '''UPP<sup>cc</sup>''' is one of two communication complexity analogues of [[Complexity Zoo:P#pp|PP]]. | Defined by [[zooref#bfs86|[BFS86]]], '''UPP<sup>cc</sup>''' is one of two communication complexity analogues of [[Complexity Zoo:P#pp|PP]]. | ||

− | UPP<sup>cc</sup> is the class of all | + | UPP<sup>cc</sup> is the class of all functions <math>f : \{0,1\}^n \times \{0,1\}^n \to \{0,1\}</math> that are computable by polylogarithmic protocols using private (but no public) randomness, which accept with probability strictly greater than 1/2 when <math>f(x,y) = 1</math> 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 [[Complexity Zoo:Symbols#paritypcc|⊕P<sup>cc</sup>]] [[zooref#for02|[For02]]]. | ||

+ | |||

+ | Does not contain [[Complexity Zoo:P#phcc|PH<sup>cc</sup>]] [[zooref#rs10|[RS10]]]. | ||

+ | |||

+ | The complexity measure associated with UPP<sup>cc</sup> is equivalent to the log of the sign-rank of the communication matrix (assuming the latter has {1,-1} entries) [[zooref#ps86|[PS86]]]. | ||

''See also:'' [[Complexity Zoo:P#ppcc|PP<sup>cc</sup>]]. | ''See also:'' [[Complexity Zoo:P#ppcc|PP<sup>cc</sup>]]. | ||

Line 87: | Line 134: | ||

Contains [[Complexity Zoo:C#conp|coNP]]. | Contains [[Complexity Zoo:C#conp|coNP]]. | ||

+ | |||

+ | ---- | ||

+ | |||

+ | ===== <span id="usbpcc" style="color:red">USBP<sup>cc</sup></span>: Unrestricted Communication Analogue of [[#sbp|SBP]] ===== | ||

+ | |||

+ | Syntactically, this has the same relationship to [[Complexity Zoo:S#sbpcc|SBP<sup>cc</sup>]] as [[Complexity Zoo:U#uppcc|UPP<sup>cc</sup>]] does to [[Complexity Zoo:P#ppcc|PP<sup>cc</sup>]]; 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<sup>cc</sup>=[[Complexity Zoo:S#sbpcc|SBP<sup>cc</sup>]] [[zooref#glm+15|[GLM+15]]]. | ||

+ | |||

+ | ---- | ||

+ | |||

+ | ===== <span id="uwappcc" style="color:red">UWAPP<sup>cc</sup></span>: Unrestricted Communication Analogue of [[#wapp|WAPP]] ===== | ||

+ | |||

+ | Syntactically, this has the same relationship to [[Complexity Zoo:W#wappcc|WAPP<sup>cc</sup>]] as [[Complexity Zoo:U#uppcc|UPP<sup>cc</sup>]] does to [[Complexity Zoo:P#ppcc|PP<sup>cc</sup>]]; 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<sup>cc</sup> protocols can be efficiently simulated by [[Complexity Zoo:W#wappcc|WAPP<sup>cc</sup>]] protocols with a slightly larger ε parameter [[zooref#glm+15|[GLM+15]]]. |

## Latest revision as of 00:03, 10 June 2016

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

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

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

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^{2}(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 that are computable by polylogarithmic protocols using private (but no public) randomness, which 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.

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