Difference between revisions of "Complexity Zoo:U"

From Complexity Zoo
Jump to navigation Jump to search
 
(3 intermediate revisions by the same user not shown)
Line 4: Line 4:
  
 
===== <span id="uamcc" style="color:red">UAM<sup>cc</sup></span>: Unambiguous Arthur-Merlin Communication Complexity =====
 
===== <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>]].
  
 
----
 
----
Line 34: 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 52: 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]].
 
----
 
===== <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 87: Line 95:
 
<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.
 
<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>
 
</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]]].
  
 
----
 
----
Line 95: Line 105:
  
 
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]]].
 
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>]].
  
 
----
 
----

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


UAMcc - UAP - UCC - UCFL - UE - UL - UL/poly - UP - UPcc - UPostBPPcc - UPPcc - US - USBPcc - UWAPPcc


UAMcc: Unambiguous Arthur-Merlin Communication Complexity

Similar to AMcc 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 NPcc [GPW16a].

Is not contained in SBPcc [GPW16a], [GLM+15].

Is contained in PostBPPcc.


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


UPcc: Communication Complexity UP

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:

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

The quadratic overhead in simulating UPcc with Pcc, or equivalently the O(log2(n)) protocol for CISG, is known to be essentially optimal [GPW15].


UPostBPPcc: Unrestricted Communication Analogue of PostBPP

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

Contains PNPcc and hence does not equal PostBPPcc since it has been shown that PNPcc is not contained in PPcc much less in PostBPPcc [BVW07].

Contained in UPPcc.


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 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 ⊕Pcc [For02].

Does not contain PHcc [RS10].

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

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

Contains coNP.


USBPcc: Unrestricted Communication Analogue of SBP

Syntactically, this has the same relationship to SBPcc as UPPcc does to PPcc; 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 USBPcc=SBPcc [GLM+15].


UWAPPcc: Unrestricted Communication Analogue of WAPP

Syntactically, this has the same relationship to WAPPcc as UPPcc does to PPcc; 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 UWAPPcc protocols can be efficiently simulated by WAPPcc protocols with a slightly larger ε parameter [GLM+15].