https://complexityzoo.net/api.php?action=feedcontributions&user=JumpDiscont&feedformat=atomComplexity Zoo - User contributions [en]2024-03-28T12:13:44ZUser contributionsMediaWiki 1.35.0https://complexityzoo.net/index.php?title=Complexity_Zoo:U&diff=6328Complexity Zoo:U2015-07-04T12:18:42Z<p>JumpDiscont: /* UL: Unambiguous L */ mentioned directed planar reachability problem</p>
<hr />
<div>__NOTOC__<br />
{{CZ-Letter-Menu|U}}<br />
<br />
<br />
===== <span id="uap" style="color:red">UAP</span>: Unambiguous Alternating Polynomial-Time =====<br />
Same as [[Complexity Zoo:A#ap|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.<br />
<br />
Contains [[#up|UP]].<br />
<br />
Defined in [[zooref#nr98|[NR98]]], where it was also shown that, even though [[Complexity Zoo:A#ap|AP]] = [[Complexity Zoo:P#pspace|PSPACE]], it is unlikely that the same is true for UAP, since UAP is contained in [[Complexity Zoo:S#spp|SPP]].<br />
<br />
[[zooref#cgr04|[CGR+04]]] have also shown that UAP<sup>UAP</sup> = UAP, and that UAP contains [[Complexity_Garden#graph_isomorphism|Graph Isomorphism]] problem.<br />
<br />
----<br />
<br />
===== <span id="ucc" style="color:red">UCC</span>: Unique Connected Component =====<br />
The class of problems reducible in [[Complexity Zoo:L#l|L]] to the problem of whether an undirected graph has a unique connected component.<br />
<br />
See [[zooref#ag00|[AG00]]] for more information.<br />
<br />
Equals [[Complexity Zoo:L#l|L]]. [[zooref#rei00|[Rei04]]]<br />
<br />
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.<br />
<br />
----<br />
<br />
===== <span id="ucfl" style="color:red">UCFL</span>: Unambiguous [[Complexity Zoo:C#cfl|CFL]] =====<br />
<br />
The class of context-free languages which can be represented by grammars where each word in the language has exactly one leftmost derivation.<br />
<br />
Strictly contains [[Complexity Zoo:D#dcfl|Deterministic CFL]]. Strictly contained in [[Complexity Zoo:C#cfl|CFL]].<br />
<br />
----<br />
<br />
===== <span id="ul" style="color:red">UL</span>: Unambiguous [[Complexity Zoo:L#l|L]] =====<br />
Has the same relation to [[Complexity Zoo:L#l|L]] as [[#up|UP]] does to [[Complexity Zoo:P#p|P]].<br />
<br />
The problem of reachability in directed <i>planar</i> graphs lies in UL [[zooref#ses05|[SES05]]].<br />
<br />
If UL = [[Complexity Zoo:N#nl|NL]], then [[Complexity Zoo:F#fnl|FNL]] is contained in [[Complexity Zoo:Symbols#sharpl|#L]] [[zooref#aj93|[AJ93]]].<br />
<br />
----<br />
<br />
===== <span id="ulpoly" style="color:red">UL/poly</span>: Nonuniform [[#ul|UL]] =====<br />
Has the same relation to [[#ul|UL]] as [[Complexity Zoo:P#ppoly|P/poly]] does to [[Complexity Zoo:P#p|P]].<br />
<br />
Equals [[Complexity Zoo:N#nlpoly|NL/poly]] [[zooref#ra00|[RA00]]]. (A corollary is that UL/poly is closed under complement).<br />
<br />
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]].<br />
<br />
----<br />
===== <span id="ue" style="color:red">UE</span>: Unambiguous Exponential-Time With Linear Exponent =====<br />
Has the same relation to [[Complexity Zoo:E#e|E]] as [[#up|UP]] does to [[Complexity Zoo:P#p|P]].<br />
<br />
----<br />
===== <span id="up" style="color:red">UP</span>: Unambiguous Polynomial-Time =====<br />
The class of decision problems solvable by an [[Complexity Zoo:N#np|NP]] machine such that<br />
<ol><br />
<li>If the answer is 'yes,' exactly one computation path accepts.</li><br />
<li>If the answer is 'no,' all computation paths reject.</li><br />
</ol><br />
Defined by [[zooref#val76|[Val76]]].<br />
<br />
"Worst-case" one-way functions exist if and only if [[Complexity Zoo:P#p|P]] does not equal UP ([[zooref#gs88|[GS88]]] and independently [[zooref#ko85|[Ko85]]]). "Worst-case" one-way permutations exist if and only if [[Complexity Zoo:P#p|P]] does not equal UP &#8745; [[Complexity Zoo:C#coup|coUP]] [[zooref#ht03|[HT03]]]. Note that these are weaker than the one-way functions and permutations that are needed for cryptographic applications.<br />
<br />
There exists an oracle relative to which [[Complexity Zoo:P#p|P]] is strictly contained in UP is strictly contained in [[Complexity Zoo:N#np|NP]] [[zooref#rac82|[Rac82]]]; indeed, these classes are distinct with probability 1 relative to a random oracle [[zooref#bei89|[Bei89]]].<br />
<br />
[[Complexity Zoo:N#np|NP]] is contained in [[Complexity Zoo:R#rp|RP]]<sup>[[Complexity Zoo:P#promiseup|PromiseUP]]</sup> [[zooref#vv86|[VV86]]]. On the other hand, [[zooref#bbf98|[BBF98]]] give an oracle relative to which [[Complexity Zoo:P#p|P]] = UP but still [[Complexity Zoo:P#p|P]] does not equal [[Complexity Zoo:N#np|NP]].<br />
<br />
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.<br />
<br />
----<br />
<br />
===== <span id="uppcc" style="color:red">UPP<sup>cc</sup></span>: Unrestricted Communication Analogue of [[Complexity Zoo:P#pp|PP]] =====<br />
Defined by [[zooref#bfs86|[BFS86]]], '''UPP<sup>cc</sup>''' is one of two communication complexity analogues of [[Complexity Zoo:P#pp|PP]].<br />
UPP<sup>cc</sup> is the class of all languages defined by functions <math>f : \{0,1\}^n \times \{0,1\}^n \to \{0,1\}</math> which are computable by polylogarithmic protocols that 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.<br />
<br />
''See also:'' [[Complexity Zoo:P#ppcc|PP<sup>cc</sup>]].<br />
<br />
----<br />
<br />
===== <span id="us" style="color:red">US</span>: Unique Polynomial-Time =====<br />
The all-American counting class.<br />
<br />
The class of decision problems solvable by an [[Complexity Zoo:N#np|NP]] machine such that the answer is 'yes' if and only if exactly one computation path accepts.<br />
<br />
In contrast to [[#up|UP]], a machine can legally have more than one accepting path - that just means that the corresponding input is not in the language.<br />
<br />
Defined in [[zooref#bg82|[BG82]]].<br />
<br />
Contains [[Complexity Zoo:C#conp|coNP]].</div>JumpDisconthttps://complexityzoo.net/index.php?title=Complexity_Zoo_References&diff=6327Complexity Zoo References2015-07-04T12:14:00Z<p>JumpDiscont: /* S */ added reference to directed planar reachability</p>
<hr />
<div>__NOTOC__<br />
<br />
{{Simple-Alpha-Menu|{{CZ-Navbar}}<br />
----<br />
}}<br />
<br />
<br />
<!-- don't delete blank lines above this.. they're there for spacing reasons --><br />
<br />
===== A =====<br />
<span id="aar02" style="color:maroon">[Aar02]</span><br />
S. Aaronson.<br />
Quantum lower bound for the collision problem,<br />
<i>Proceedings of ACM STOC'2002</i>, pp. 635-642, 2002.<br />
arXiv:[http://arxiv.org/abs/quant-ph/0111102 quant-ph/0111102].<br />
<br />
<span id="aar03" style="color:maroon">[Aar03]</span><br />
S. Aaronson.<br />
Lower bounds for local search by quantum arguments,<br />
<i>Proceedings of ACM STOC 2004</i>.<br />
arXiv:[http://arxiv.org/abs/quant-ph/0307149 quant-ph/0307149],<br />
ECCC [http://eccc.uni-trier.de/eccc-reports/2003/TR03-057/ TR03-057].<br />
<br />
<span id="aar03b" style="color:maroon">[Aar03b]</span><br />
S. Aaronson.<br />
Multilinear formulas and skepticism of quantum computing,<br />
<i>Proceedings of ACM STOC 2004</i>.<br />
arXiv:[http://arxiv.org/abs/quant-ph/0311039 quant-ph/0311039],<br />
ECCC [http://eccc.uni-trier.de/eccc-reports/2003/TR03-079/ TR03-079].<br />
<br />
<span id="aar04b" style="color:maroon">[Aar04b]</span><br />
S. Aaronson.<br />
Limitations of quantum advice and one-way communication,<br />
<i>Proceedings of IEEE Complexity 2004</i>, pp. 320-332, 2004.<br />
arXiv:[http://arxiv.org/abs/quant-ph/0402095 quant-ph/0402095],<br />
ECCC [http://eccc.uni-trier.de/eccc-reports/2004/TR04-026/ TR04-026].<br />
<br />
<span id="aar05" style="color:maroon">[Aar05]</span><br />
S. Aaronson.<br />
Quantum computing and hidden variables,<br />
<i>Physical Review A</i> 71:032325, March 2005.<br />
arXiv:[http://arxiv.org/abs/quant-ph/0408035 quant-ph/0408035].<br />
<br />
<span id="aar05b" style="color:maroon">[Aar05b]</span><br />
S. Aaronson.<br />
Quantum computing, postselection, and probabilistic polynomial-time,<br />
<i>Proceedings of the Royal Society A</i>, 461(2063):3473-3482, 2005.<br />
arXiv:[http://arxiv.org/abs/quant-ph/0412187 quant-ph/0412187].<br />
<br />
<span id="aar05c" style="color:maroon">[Aar05c]</span><br />
S. Aaronson.<br />
NP-complete problems and physical reality.<br />
<i>ACM SIGACT News</i>, March 2005<br />
[http://arxiv.org/abs/quant-ph/0502072 quant-ph/0502072].<br />
<br />
<span id="aar06" style="color:maroon">[Aar06]</span><br />
S. Aaronson.<br />
Oracles are subtle but not malicious,<br />
<i>Proceedings of IEEE Complexity 2006</i>, 2006.<br />
arXiv:[http://arxiv.org/abs/cs.CC/0504048 cs.CC/0504048],<br />
ECCC [http://eccc.uni-trier.de/eccc-reports/2004/TR05-040/ TR05-040].<br />
<br />
<span id="aar06b" style="color:maroon">[Aar06b]</span><br />
S. Aaronson.<br />
QMA/qpoly is contained in PSPACE/poly: de-Merlinizing quantum protocols,<br />
<i>Proceedings of IEEE Complexity 2006</i>, 2006.<br />
arXiv:[http://arxiv.org/abs/quant-ph/0510230 quant-ph/0510230].<br />
<br />
<span id="ak06" style="color:maroon">[AK06]</span><br />
S. Aaronson and G. Kuperberg.<br />
Quantum versus classical proofs and advice,<br />
submitted, 2006.<br />
arXiv:[http://arxiv.org/abs/quant-ph/0604056 quant-ph/0604056].<br />
<br />
<span id="abjl2014" style="color:maroon">[ABFL2014]</span><br />
S. Aaronson, A. Bouland, J. Fitzsimons, M. Lee<br />
The space "just above" BQP<br />
arXiv:[http://arxiv.org/abs/1412.6507 arxiv.org/abs/1412.6507]<br />
<br />
<span id="ab00" style="color:maroon">[AB00]</span><br />
E. Allender and D. A. M. Barrington.<br />
Uniform Circuits for Division: Consequences and Problems.<br />
J. Comput. System Sci. 65 (2002), no. 4, 695--716.<br />
ECCC [http://eccc.uni-trier.de/eccc-reports/2000/TR00-65/ TR00-65], 2000.<br />
<br />
{{Reference<br />
|id=abd08 |tag=ABD+08<br />
|authors=S. Aaronson, S. Beigi, A. Drucker, et al<br />
|title=The power of unentanglement<br />
|journal=Electronic Colloquium on Computational Complexity<br />
|srcdetail=ECCC Report TR08-051, accepted on May 02, 2008<br />
|link=[http://eccc.hpi-web.de/eccc-reports/2008/TR08-051/index.html http://eccc.hpi-web.de/eccc-reports/2008/TR08-051/index.html]<br />
}}<br />
<br />
<span id="abf94" style="color:maroon">[ABF+94]</span><br />
J. Aspnes, R. Beigel, M. L. Furst, and S. Rudich.<br />
The expressive power of voting polynomials,<br />
<i>Combinatorica</i> 14(2):135-148, 1994.<br />
[http://www.cs.yale.edu/~aspnes/stoc91voting.ps http://www.cs.yale.edu/~aspnes/stoc91voting.ps]<br />
<br />
<span id="abk02" style="color:maroon">[ABK+02]</span><br />
E. Allender, H. Buhrman, M. Kouck&yacute;, D. van Melkebeek, and D. Ronneburger.<br />
Power from random strings,<br />
<i>Proceedings of IEEE FOCS'2002</i>, pp. 669-678, 2002.<br />
ECCC [http://eccc.uni-trier.de/eccc-reports/2002/TR02-028/ TR02-028].<br />
<br />
<span id="abl98" style="color:maroon">[ABL98]</span><br />
A. Ambainis, D. M. Barrington, and H. L&ecirc;Thanh.<br />
On counting AC<sup>0</sup> circuits with negative constants,<br />
<i>Proceedings of MFCS (Mathematical Foundations of Computer Science)</i>, pp. 419-427, 1998.<br />
ECCC [http://eccc.uni-trier.de/eccc-reports/1998/TR98-020/ TR98-020].<br />
<br />
<span id="abo99" style="color:maroon">[ABO99]</span><br />
E. Allender, R. Beals, and M. Ogihara.<br />
The complexity of matrix rank and feasible systems of linear equations,<br />
<i>Computational Complexity</i> 8(2):99-126, 1999.<br />
ECCC [http://eccc.uni-trier.de/eccc-reports/1996/TR96-024/ TR96-024],<br />
DIMACS [http://dimacs.rutgers.edu/TechnicalReports/abstracts/1997/97-40.html TR 97-40].<br />
<br />
<span id="abv95" style="color:maroon">[ABV95]</span><br />
W. Aiello, M. Bellare, and R. Venkatesan.<br />
Knowledge on the average - perfect, statistical, and logarithmic,<br />
<i>Proceedings of ACM STOC'95</i>, 1995.<br />
<br />
<span id="acg99" style="color:maroon">[ACG+99]</span><br />
G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi.<br />
<i>Complexity and Approximation: Combinatorial optimization problems and their approximability properties</i>,<br />
Springer-Verlag, 1999.<br />
See also "A compendium of NP optimization problems" (P. Crescenzi and V. Kann, eds.),<br />
[http://www.nada.kth.se/~viggo/wwwcompendium/ http://www.nada.kth.se/~viggo/wwwcompendium/].<br />
<br />
<span id="adh97" style="color:maroon">[ADH97]</span><br />
L. Adleman, J. DeMarrais, and M. Huang.<br />
Quantum computability,<br />
<i>SIAM Journal on Computing</i> 26:1524-1540, 1997.<br />
<br />
<span id="adl78" style="color:maroon">[Adl78]</span><br />
L. Adleman.<br />
Two theorems on random polynomial time.<br />
FOCS 78.<br />
<br />
<span id="afm01" style="color:maroon">[AFM01]</span><br />
L. Antu&ntilde;es, L. Fortnow, and D. van Melkebeek.<br />
Computational depth,<br />
<i>Proceedings of IEEE Complexity'01</i>, pp. 266-273, 2001.<br />
[http://people.cs.uchicago.edu/~fortnow/papers/depth.ps http://people.cs.uchicago.edu/~fortnow/papers/depth.ps]<br />
<br />
<span id="ag00" style="color:maroon">[AG00]</span><br />
C. Alvarez and R. Greenlaw.<br />
A compendium of problems complete for symmetric logarithmic space,<br />
<i>Journal of Computational Complexity</i> 9:73-95, 2000.<br />
ECCC [http://eccc.uni-trier.de/eccc-reports/1996/TR96-039/ TR96-039].<br />
<br />
<span id="ag04" style="color:maroon">[AG04]</span><br />
S. Aaronson and D. Gottesman.<br />
Improved Simulation of Stabilizer Circuits,<br />
<i>Phys. Rev. A</i> 70, 052328, 2004.<br />
[http://arxiv.org/abs/quant-ph/0406196 arXiv:quant-ph/0406196].<br />
<br />
<span id="agh90" style="color:maroon">[AGH90]</span><br />
W. Aiello, S. Goldwasser, and J. H&aring;stad.<br />
On The Power Of Interaction.<br />
Combinatorica 10 (1990), no. 1, 3--25.<br />
<br />
<span id="agk07" style="color:maroon">[AGK07]</span><br />
D. Aharonov, D. Gottesman, and J. Kempe;stad.<br />
The power of quantum systems on a line.<br />
FOCS 2007.<br />
<br />
{{Reference<br />
|tag=Agr01<br />
|authors=Agrawal, Manindra<br />
|title=For completeness, sublogarithmic space is no space<br />
|journal=Information Processing Letters (82), 2001-2002<br />
|srcdetail=iss. 6, 321-325<br />
|link=http://www.cse.iitk.ac.in/~manindra/isomorphism/sublog-completeness.pdf<br />
}}<br />
<br />
{{Reference<br />
|id=Ajt83<br />
|tag=AJT83<br />
|authors=M. Ajtai<br />
|title=Σ-1-1-Formulae on finite structures<br />
|journal=Annals of Pure and Applied Logic (24), 1983<br />
|srcdetail=1-48<br />
}}<br />
<br />
<span id="ah87" style="color:maroon">[AH87]</span><br />
L. Adleman and M. Huang.<br />
Recognizing primes in random polynomial time,<br />
<i>Proceedings of ACM STOC'87</i>, pp. 462-470, 1987.<br />
<br />
<span id="ah87b" style="color:maroon">[AH87b]</span><br />
W. Aiello and J. H&aring;stad.<br />
Perfect zero-knowledge languages can be recognized in two rounds,<br />
<i>Proceedings of IEEE FOCS 1987</i>, pp. 439-448, 1987.<br />
<br />
<span id="aik04" style="color:maroon">[AIK04]</span><br />
B. Applebaum, Y. Ishai, and E. Kushilevitz.<br />
Cryptography in NC<sup>0</sup>,<br />
<i>Proceedings of IEEE FOCS 2004</i>.<br />
[http://www.cs.technion.ac.il/~yuvali/pubs/AIK04.ps http://www.cs.technion.ac.il/~yuvali/pubs/AIK04.ps].<br />
<br />
<span id="aj93" style="color:maroon">[AJ93]</span><br />
C. Alvarez and B. Jenner.<br />
A very hard log-space counting class,<br />
<i>Theoretical Computer Science</i> 107:3-30, 1993.<br />
<br />
<span id="ak02" style="color:maroon">[AK02]</span><br />
V. Arvind and P. Kurur.<br />
Graph isomorphism is in SPP,<br />
ECCC [http://eccc.uni-trier.de/eccc-reports/2002/TR02-037/ TR02-037], 2002.<br />
<br />
<span id="ak06" style="color:maroon">[AK06]</span><br />
S. Aaronson and G. Kuperberg.<br />
Quantum Versus Classical Proofs and Advice.<br />
arXiv:[http://arxiv.org/quant-ph/0604056 quant-ph/0604056], 2006.<br />
<br />
<span id="ak96" style="color:maroon">[AK96]</span><br />
F. Ablayev and M. Karpinski.<br />
On the power of randomized branching programs,<br />
<i>Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP)</i>, Springer-Verlag 1099, pp. 348-356, 1996.<br />
ECCC [http://eccc.uni-trier.de/eccc-reports/1995/TR95-054/ TR95-054],<br />
DIMACS [http://dimacs.rutgers.edu/TechnicalReports/abstracts/1996/96-46.html TR 96-46].<br />
<br />
<span id="akl79" style="color:maroon">[AKL+79]</span><br />
R. Aleliunas, R. M. Karp, R. J. Lipton, L. Lov&aacute;sz, and C. Rackoff.<br />
Random walks, traversal sequences, and the complexity of maze problems,<br />
<i>Proceedings of IEEE FOCS'79</i>, pp. 218-223, 1979.<br />
<br />
{{Reference<br />
|tag=AKR+03<br />
|authors=E. Allender, M. Koucký, D. Ronneburger, et al<br />
|title=Derandomization and distinguishing complexity<br />
|journal=Proceedings of the 18th Annual IEEE Conference on Computational Complexity<br />
|srcdetail=209-220<br />
}}<br />
<br />
{{Reference<br />
|tag=AKS94<br />
|authors=V. Arvind, J. Köbler and R. Schuler<br />
|title=On helping and interactive proof systems<br />
|journal=Algorithms and Computation: 5th International Symposium<br />
|srcdetail=137-145<br />
}}<br />
<br />
<span id="aks02" style="color:maroon">[AKS02]</span><br />
M. Agrawal, N. Kayal, and N. Saxena.<br />
Primes is in P,<br />
Annals of Mathematics, 160 (2004), 781-793.<br />
[http://www.cse.iitk.ac.in/primality.pdf http://www.cse.iitk.ac.in/primality.pdf].<br />
<br />
<span id="aks95" style="color:maroon">[AKS+95]</span><br />
V. Arvind, J. K&ouml;bler, U. Sch&ouml;ning, and R. Schuler.<br />
If NP has polynomial-size circuits, then MA=AM,<br />
<i>Theoretical Computer Science</i> 137, 1995.<br />
[http://www.informatik.hu-berlin.de/Institut/struktur/algorithmenII/Papers/ma-am.ps.gz http://www.informatik.hu-berlin.de/Institut/struktur/algorithmenII/Papers/ma-am.ps.gz]<br />
<br />
<span id="all96" style="color:maroon">[All96]</span><br />
E. Allender.<br />
Circuit complexity before the dawn of the new millennium,<br />
<i>Proceedings of the 16th Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FST&amp;TCS)</i>, Lecture Notes in Computer Science 1180, pp. 1-18, 1996.<br />
DIMACS [http://dimacs.rutgers.edu/TechnicalReports/abstracts/1997/97-49.html TR 97-49].<br />
<br />
<span id="all99" style="color:maroon">[All99]</span><br />
E. Allender.<br />
The permanent requires large uniform threshold circuits,<br />
<i>Chicago Journal of Theoretical Computer Science</i> 7, 1999.<br />
DIMACS [http://dimacs.rutgers.edu/TechnicalReports/abstracts/1997/97-51.html TR 97-51].<br />
<br />
<span id="alm98" style="color:maroon">[ALM+98]</span><br />
S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy.<br />
Proof verification and hardness of approximation problems,<br />
<i>Journal of the ACM</i> 45(3):501-555, 1998.<br />
ECCC [http://eccc.uni-trier.de/eccc-reports/1998/TR98-008/ TR98-008].<br />
<br />
{{Reference<br />
|id=am04 |tag=AM04<br />
|title=Visibly Pushdown Languages<br />
|authors=R. Alur and P. Madhusudan<br />
|journal=Proceedings of ACM STOC'04, 2004.<br />
|srcdetail=202-211<br />
}}<br />
<br />
{{Reference<br />
|id=am09 |tag=AM09<br />
|title=Adding Nesting Structure to Words.<br />
|authors=R. Alur and P. Madhusudan<br />
|journal=Journal of the ACM 56(3)<br />
|srcdetail=Article 16, May 2009<br />
}}<br />
<br />
<span id="amp02" style="color:maroon">[AMP02]</span><br />
F. Ablayev, C. Moore, and C. Pollett.<br />
Quantum and stochastic branching programs of bounded width,<br />
<i>Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP)</i>, 2002.<br />
arXiv:[http://arxiv.org/abs/quant-ph/0201139 quant-ph/0201139],<br />
ECCC [http://eccc.uni-trier.de/eccc-reports/2002/TR02-013/ TR02-013].<br />
<br />
<span id="ams06" style="color:maroon">[AMS06]</span><br />
N. Alon, D. Moshkovitz, and S. Safra. <br />
Algorithmic construction of sets for k-restrictions, <br />
<i>ACM Transactions on Algorithms (TALG)</i> 2(2): 153–177, 2006.<br />
[http://dx.doi.org/10.1145/1150334.1150336 doi:10.1145/1150334.1150336]<br />
<br />
<span id="an02" style="color:maroon">[AN02]</span><br />
D. Aharonov and T. Naveh.<br />
Quantum NP - a survey,<br />
arXiv:[http://arxiv.org/abs/quant-ph/0210077 quant-ph/0210077].<br />
<br />
<span id="ap95" style="color:maroon">[AP95]</span><br />
G. Ausiello and M. Protasi<br />
Local search, reducibility, and approximability of NP optimization problems,<br />
<i>Information Processing Letters</i> 54:73-79, 1995.<br />
<br />
<span id="ar01" style="color:maroon">[AR01]</span><br />
M. Alekhnovich and A. A. Razborov.<br />
Resolution is not automatizable unless W[P] is tractable,<br />
<i>Proceedings of IEEE FOCS'01</i>, pp. 210-219, 2001.<br />
<br />
<span id="ar03" style="color:maroon">[AR03]</span><br />
D. Aharonov and O. Regev.<br />
A lattice problem in quantum NP,<br />
arXiv:[http://arxiv.org/abs/quant-ph/0307220 quant-ph/0307220].<br />
<br />
<span id="ar88" style="color:maroon">[AR88]</span><br />
E. Allender and R. Rubinstein.<br />
P-printable sets,<br />
<i>SIAM Journal on Computing</i> 17(6):1193-1202, 1988.<br />
<br />
<span id="aro96" style="color:maroon">[Aro96]</span><br />
S. Arora.<br />
Polynomial time approximation scheme for Euclidean TSP and other geometric problems,<br />
<i>Proceedings of IEEE FOCS'96</i>, pp. 2-11, 1996.<br />
[http://www.cs.princeton.edu/~arora/pubs/tsp1.ps http://www.cs.princeton.edu/~arora/pubs/tsp1.ps]<br />
<br />
<span id="arz99" style="color:maroon">[ARZ99]</span><br />
E. Allender, K. Reinhardt, and S. Zhou.<br />
Isolation, matching, and counting: uniform and nonuniform upper bounds,<br />
<i>Journal of Computer and System Sciences</i> 59:164-181, 1999.<br />
[http://www.cs.rutgers.edu/pub/allender/matching.pdf http://www.cs.rutgers.edu/pub/allender/matching.pdf].<br />
<br />
<span id="as94" style="color:maroon">[AS94]</span><br />
E. Allender and M. Strauss.<br />
Measure on small complexity classes with applications for BPP,<br />
<i>Proceedings of IEEE FOCS'94</i>, pp. 807-818, 1994.<br />
ECCC [http://eccc.uni-trier.de/eccc-reports/1994/TR94-004/ TR94-004],<br />
DIMACS [http://dimacs.rutgers.edu/TechnicalReports/abstracts/1994/94-18.html TR 94-18].<br />
<br />
<span id="as98" style="color:maroon">[AS98]</span><br />
S. Arora and M. Safra.<br />
Probabilistic checking of proofs: a new characterization of NP,<br />
<i>Journal of the ACM</i> 45(1):70-122, 1998.<br />
[http://www.cs.princeton.edu/~arora/pubs/as.ps http://www.cs.princeton.edu/~arora/pubs/as.ps].<br />
<br />
<span id="asv00" style="color:maroon">[ASV00]</span><br />
A. Ambainis, L. Schulman, and U. Vazirani.<br />
Quantum computing with highly mixed states,<br />
<i>Proceedings of ACM STOC'2000</i>, pp. 705-714, 2000.<br />
arXiv:[http://arxiv.org/abs/quant-ph/0003136 quant-ph/0003136].<br />
<br />
<span id="atw00" style="color:maroon">[ATW+00]</span><br />
R. Armoni, A. Ta-Shma, A. Wigderson, and S. Zhou.<br />
An O(log(n)<sup>4/3</sup>) algorithm for (s,t) connectivity in undirected graphs,<br />
<i>Journal of the ACM</i> 47(2):294-311, 2000.<br />
[http://whiteboard.cs.tau.ac.il/~amnon/Papers/ATWZ.jacm00.pdf http://whiteboard.cs.tau.ac.il/~amnon/Papers/ATWZ.jacm00.pdf]<br />
<br />
{{Reference<br />
|tag=AV04<br />
|title=Abelian permutation group problems and logspace counting classes<br />
|authors=V. Arvind and T. C. Vijayaraghavan<br />
|journal=Proceedings of the 19th IEEE Conference on Computational Complexity<br />
|srcdetails=204-214, 2004<br />
}}<br />
<br />
<span id="aw90" style="color:maroon">[AW90]</span><br />
E. Allender and K. W. Wagner.<br />
Counting hierarchies: polynomial time and constant depth circuits,<br />
<i>Bulletin of the EATCS</i> 40, February 1990.<br />
[http://people.cs.uchicago.edu/~fortnow/beatcs/column40.ps http://people.cs.uchicago.edu/~fortnow/beatcs/column40.ps].<br />
<br />
===== B =====<br />
<br />
<span id="babai85" style="color:maroon">[Bab85]</span><br />
L. Babai.<br />
Trading Group Theory for Randomness.<br />
In <i>17th STOC</i>, pages 421--429, 1985.<br />
<br />
<span id="bab87" style="color:maroon">[Bab87]</span><br />
L. Babai.<br />
Random oracles separate PSPACE from the polynomial-time hierarchy.<br />
Information Processing Letters, 26 (1987) 51-53.<br />
<br />
<span id="bar02" style="color:maroon">[Bar02]</span><br />
B. Barak.<br />
A probabilistic-time hierarchy theorem for "slightly non-uniform" algorithms,<br />
<i>Proceedings of RANDOM'2002</i>, 2002.<br />
[http://www.math.weizmann.ac.il/~/boaz/Papers/bptime.ps http://www.math.weizmann.ac.il/~/boaz/Papers/bptime.ps]<br />
<br />
<span id="bar89" style="color:maroon">[Bar89]</span><br />
D. A. M. Barrington.<br />
Bounded-width polynomial-size branching programs can recognize exactly those languages in NC<sub>1</sub>,<br />
<i>Journal of Computer and System Sciences</i> 38:150-164, 1989.<br />
<br />
<span id="baz95" style="color:maroon">[Baz95]</span><br />
C. Bazgan.<br />
Approximation de probl&egrave;mes d'optimisation et de fonctions totales de NP,<br />
PhD thesis, INRIA, Orsay, France, 1998.<br />
[http://l1.lamsade.dauphine.fr/~bazgan/Papers/these.ps http://l1.lamsade.dauphine.fr/~bazgan/Papers/these.ps]<br />
<br />
<span id="bb92" style="color:maroon">[BB92]</span><br />
A. Berthiaume and G. Brassard.<br />
The quantum challenge to structural complexity theory.<br />
Proceedings of Structure in Complexity Theory, 1992, 132--137.<br />
<br />
<span id="bbb97" style="color:maroon">[BBB+97]</span><br />
C. H. Bennett, E. Bernstein, G. Brassard, and U. Vazirani.<br />
Strengths and weaknesses of quantum computing,<br />
<i>SIAM Journal on Computing</i>, 26(5):1510-1523, 1997.<br />
arXiv:[http://arxiv.org/abs/quant-ph/9701001 quant-ph/9701001].<br />
<br />
<span id="bbf98" style="color:maroon">[BBF98]</span><br />
R. Beigel, H. Buhrman, and L. Fortnow.<br />
NP might not be as easy as detecting unique solutions,<br />
<i>Proceedings of ACM STOC'98</i>, pp. 203-208, 1998.<br />
[http://people.cs.uchicago.edu/~fortnow/papers/newiso.ps http://people.cs.uchicago.edu/~fortnow/papers/newiso.ps].<br />
<br />
<span id="bbr94" style="color:maroon">[BBR94]</span><br />
D. A. M. Barrington, R. Beigel, and S. Rudich.<br />
Representing Boolean functions as polynomials modulo composite integers,<br />
<i>Computational Complexity</i>, 4:367-382, 1994.<br />
[http://www.cis.temple.edu/~beigel/papers/bbr-mods-cc.html http://www.cis.temple.edu/~beigel/papers/bbr-mods-cc.html].<br />
<br />
<span id="bbs86" style="color:maroon">[BBS86]</span><br />
J. Balc&aacute;zar, R. Book, and U. Sch&ouml;ning.<br />
Sparse sets, lowness, and highness,<br />
<i>SIAM Journal on Computing</i> 15:739-747, 1986.<br />
<br />
<span id="bce95" style="color:maroon">[BCE+95]</span><br />
P. Beame, S. Cook, J. Edmonds, R. Impagliazzo, and T. Pitassi.<br />
The relative complexity of NP search problems,<br />
<i>Proceedings of ACM STOC'95</i>, pp. 303-314, 1995.<br />
[http://www.cs.washington.edu/homes/beame/search.ps http://www.cs.washington.edu/homes/beame/search.ps]<br />
<br />
<span id="bch86" style="color:maroon">[BCH86]</span><br />
P. Beame, S. Cook, and J. Hoover.<br />
Log depth circuits for division and related problems,<br />
<i>SIAM Journal on Computing</i> 15:994-1003, 1986<br />
[http://www.cs.washington.edu/homes/beame/papers/division.ps http://www.cs.washington.edu/homes/beame/papers/division.ps].<br />
<br />
<span id="bcg92" style="color:maroon">[BCG+92]</span><br />
S. Ben-David, B. Chor, O. Goldreich, and M. Luby.<br />
On the theory of average case complexity,<br />
<i>Journal of Computer and System Sciences</i> 44(2):193-219, 1992.<br />
[http://www.cs.technion.ac.il/~shai/aver.pdf http://www.cs.technion.ac.il/~shai/aver.pdf]<br />
<br />
<span id="bcs97" style="color:maroon">[BCS+97]</span><br />
L. Blum, F. Cucker, M. Shub, and S. Smale.<br />
<i>Complexity and Real Computation</i>,<br />
Springer-Verlag, 1997.<br />
<br />
<span id="bcd89" style="color:maroon">[BCD+89]</span><br />
A. Borodin, S. A. Cook, P. W. Dymond, W. L. Ruzzo, and M. L. Tompa.<br />
Two applications of inductive counting for complementation problems,<br />
<i>SIAM Journal on Computing</i> 18:559-578, 1989.<br />
<br />
<span id="bcp83" style="color:maroon">[BCP83]</span><br />
A. Borodin, S. A. Cook, and N. Pippenger.<br />
Parallel computations for well-endowed rings and space-bounded probabilistic machines,<br />
<i>Information and Control</i> 58:113-136, 1983.<br />
<br />
<span id="bd99" style="color:maroon">[BD99]</span><br />
H. Buhrman and W. van Dam.<br />
Bounded quantum query complexity,<br />
<i>Proceedings of IEEE Complexity'99</i>, pp. 149-156, 1999.<br />
arXiv:[http://arxiv.org/abs/quant-ph/9903035 quant-ph/9903035].<br />
<br />
<span id="bdg88" style="color:maroon">[BDG88]</span><br />
J. L. Balc&aacute;zar, J. D&iacute;az, and J. Gabarr&oacute;<br />
Structural complexity 1<br />
<br />
<span id="bdh92" style="color:maroon">[BDH+92]</span><br />
G. Buntrock, C. Damm, U. Hertrampf, and Ch. Meinel.<br />
Structure and importance of logspace-MOD-classes,<br />
<i>Mathematical Systems Theory</i> 25:223-237, 1992.<br />
[http://www.num.math.uni-goettingen.de/damm/papers/BDHM92.ps.gz http://www.num.math.uni-goettingen.de/damm/papers/BDHM92.ps.gz].<br />
<br />
<span id="bei89" style="color:maroon">[Bei89]</span><br />
R. Beigel.<br />
On the relativized power of additional accepting paths,<br />
<i>Proceedings of IEEE Complexity'89</i>, pp. 216-224, 1989.<br />
[http://www.cis.temple.edu/~beigel/papers/ukp-structures.PS.gz http://www.cis.temple.edu/~beigel/papers/ukp-structures.PS.gz].<br />
<br />
<span id="bei94" style="color:maroon">[Bei94]</span><br />
R. Beigel.<br />
Perceptrons, PP, and the polynomial hierarchy,<br />
<i>Computational Complexity</i> 4:339-349, 1994.<br />
[http://www.cis.temple.edu/~beigel/papers/delta2p-cc.PS.gz http://www.cis.temple.edu/~beigel/papers/delta2p-cc.PS.gz].<br />
<br />
<span id="ber80" style="color:maroon">[Ber80]</span><br />
L. Berman.<br />
The complexity of logical theories,<br />
<i>Theoretical Computer Science</i> 11:71-78, 1980.<br />
<br />
<span id="bf92" style="color:maroon">[BF92]</span><br />
R. Beigel and J. Feigenbaum.<br />
On Being Incoherent Without Being Very Hard.<br />
Comput. Complexity 2 (1992), no. 1, 1--17<br />
[http://www.cis.temple.edu/~beigel/papers/bf-coherent-cc.html http://www.cis.temple.edu/~beigel/papers/bf-coherent-cc.html]<br />
<br />
<span id="bf99" style="color:maroon">[BF99]</span><br />
H. Buhrman and L. Fortnow.<br />
One-sided versus two-sided randomness,<br />
<i>Proceedings of the 16th Symposium on Theoretical Aspects of Computer Science (STACS)</i>, pp. 100-109, 1999.<br />
[http://people.cs.uchicago.edu/~fortnow/papers/rpvsbpp.ps http://people.cs.uchicago.edu/~fortnow/papers/rpvsbpp.ps].<br />
<br />
{{Reference<br />
|tag=BF03<br />
|authors=R. Beigel<br />
|title=Are Cook and Karp ever the same?<br />
|journal=Proceedings of the 18th Annual IEEE Conference on Computational Complexity<br />
|srcdetail=333-336<br />
}}<br />
<br />
<span id="bfl91" style="color:maroon">[BFL91]</span><br />
L. Babai, L. Fortnow, and C. Lund.<br />
Nondeterministic exponential time has two-prover interactive protocols,<br />
<i>Computational Complexity</i> 1:3-40, 1991.<br />
[http://people.cs.uchicago.edu/~fortnow/papers/mip2.ps http://people.cs.uchicago.edu/~fortnow/papers/mip2.ps].<br />
<br />
<span id="bfm88" style="color:maroon">[BFM88]</span><br />
M. Blum, P. Feldman, and S. Micali. <br />
Non-interactive zero-knowledge proofs and their applications,<br />
<i>Proceedings of the 20th STOC, ACM</i>, 1988.<br />
<br />
<span id="bfs86" style="color:maroon">[BFS86]</span><br />
L. Babai, P. Frankl, and J. Simon.<br />
Complexity classes in communication complexity theory,<br />
<i>Proceedings of IEEE FOCS'86</i>, pp. 337-347, 1986.<br />
<br />
<span id="bft98" style="color:maroon">[BFT98]</span><br />
H. Buhrman, L. Fortnow, and T. Thierauf.<br />
Nonrelativizing separations,<br />
<i>Proceedings of IEEE Complexity'98</i>, pp. 8-12, 1998.<br />
[http://people.cs.uchicago.edu/~fortnow/papers/nonrel.ps http://people.cs.uchicago.edu/~fortnow/papers/nonrel.ps].<br />
<br />
<span id="bgs75" style="color:maroon">[BGS75]</span><br />
T. Baker, J. Gill, and R. Solovay.<br />
Relativizations of the P=?NP question,<br />
<i>SIAM Journal on Computing</i> 4:431-442, 1975.<br />
<br />
<span id="bh77" style="color:maroon">[BH77]</span><br />
L. Berman and J. Hartmanis.<br />
On isomorphism and density of NP and other complete sets,<br />
<i>SIAM Journal on Computing</i> 6:305-322, 1977.<br />
<br />
<span id="bg03" style="color:maroon">[BG03]</span><br />
M. Ben-Or and D. Gutfreund.<br />
Trading help for interaction in statistical zero-knowledge proofs,<br />
<i>J. Cryptology</i> 16 (2003), no. 2, 95--116.<br />
[http://www.cs.huji.ac.il/~danig/pubs/help_interaction.ps http://www.cs.huji.ac.il/~danig/pubs/help_interaction.ps]<br />
<br />
<span id="bg69" style="color:maroon">[BG69]</span><br />
R. Book and S. Greibach.<br />
Quasi-realtime languages,<br />
<i>Proceedings of ACM STOC</i> pp. 15-18, 1969.<br />
http://portal.acm.org/citation.cfm?id=800169.805416<br />
<br />
<span id="bg81" style="color:maroon">[BG81]</span><br />
C. H. Bennett and J. Gill.<br />
Relative to a random oracle A, P<sup>A</sup> != NP<sup>A</sup> != coNP<sup>A</sup> with probability 1,<br />
<i>SIAM Journal on Computing</i>, 10(1):96-113, 1981.<br />
DOI:[http://dx.doi.org/10.1137/0210008 10.1137/0210008]<br />
<br />
<span id="bg92" style="color:maroon">[BG92]</span><br />
R. Beigel and J. Gill.<br />
Counting classes: thresholds, parity, mods, and fewness,<br />
<i>Theoretical Computer Science</i> 103(1):3-23, 1992.<br />
[http://www.cis.temple.edu/~beigel/papers/bg-mods-tcs.PS.gz http://www.cis.temple.edu/~beigel/papers/bg-mods-tcs.PS.gz].<br />
<br />
<span id="bg98" style="color:maroon">[BG98]</span><br />
R. Beigel and J. Goldsmith.<br />
Downward separation fails catastrophically for limited nondeterminism classes,<br />
<i>SIAM Journal on Computing</i> 17(5):1420-1429, 1998.<br />
[http://www.cis.temple.edu/~beigel/papers/bg-beta-draft.PS.gz http://www.cis.temple.edu/~beigel/papers/bg-beta-draft.PS.gz].<br />
<br />
<span id="bg94" style="color:maroon">[BG94]</span><br />
M. Bellare and S. Goldwasser.<br />
The complexity of decision versus search,<br />
<i>SIAM Journal on Computing</i> 23(1):91-119, 1994.<br />
[http://www.cs.ucsd.edu/users/mihir/papers/compip.pdf http://www.cs.ucsd.edu/users/mihir/papers/compip.pdf]<br />
<br />
<span id="bgg90" style="color:maroon">[BGG+90]</span><br />
M. Ben-Or, O. Goldreich, S. Goldwasser, J. H&aring;stad, J. Kilian, S. Micali, and P. Rogaway.<br />
Everything provable is provable in zero-knowledge,<br />
<i>Advances in Cryptology: CRYPTO'88</i> (S. Goldwasser, ed.), Lecture Notes in Computer Science 403, Springer-Verlag, pp. 37-56, 1990.<br />
<br />
<span id="bgk88" style="color:maroon">[BGK+88]</span><br />
M. Ben-Or, S. Goldwasser, J. Kilian, and A. Wigderson.<br />
Multi-prover interactive proofs: how to remove intractability,<br />
<i>Proceedings of ACM STOC'88</i>, pp. 113-131, 1988.<br />
<br />
<span id="bg82" style="color:maroon">[BG82]</span><br />
A. Blass and Y. Gurevich.<br />
On the unique satisfiability problem,<br />
<i>Information and Control</i> 55(1-3):80-88, 1982.<br />
<br />
<span id="bgm02" style="color:maroon">[BGM02]</span><br />
E. B&ouml;hler, C. Gla&szlig;er, and D. Meister.<br />
Error-bounded probabilistic computations between MA and AM,<br />
Mathematical foundations of computer science 2003, 249--258.<br />
[http://haegar.informatik.uni-wuerzburg.de/users/glasser/publications/sbp-ma-am-tr.pdf http://haegar.informatik.uni-wuerzburg.de/users/glasser/publications/sbp-ma-am-tr.pdf]<br />
<br />
<span id="bgr93" style="color:maroon">[BGR93]</span> <br />
Burchard von Braunmühl, Romain Gengler, Robert Rettinger.<br />
The alternation hierarchy for sublogarithmic space is infinite,<br />
Computational Complexity, v.3 n.3, p.207-230, July 1993 <br />
[doi>10.1007/BF01271368]<br />
[http://portal.acm.org/citation.cfm?id=218886]<br />
<br />
<span id="bh91" style="color:maroon">[BH91]</span><br />
S. R. Buss and L. Hay.<br />
On truth-table reducibility to SAT,<br />
<i>Information and Computation</i> 91(1):86-102, 1991.<br />
<br />
<span id="bh97" style="color:maroon">[BH97]</span><br />
C. Berg and J. H&aring;stad.<br />
On the BPP hierarchy problem,<br />
Technical Report TRITA-NA-9702, Royal Institute of Technology, Sweden, 1997.<br />
[ftp://ftp.nada.kth.se/pub/documents/Theory/Christer-Berg/bpp.ps ftp://ftp.nada.kth.se/pub/documents/Theory/Christer-Berg/bpp.ps].<br />
<br />
{{Reference<br />
|tag=BH08<br />
|title=NP-Hard sets are exponentially eense unless NP is contained in coNP/poly<br />
|journal=Electronic Colloquium on Computational Complexity<br />
|authors=H. Buhrman and J. Hitchcock <br />
|srcdetail=ECCC Report TR08-022, accepted on Mar 11, 2008<br />
|link=[http://eccc.hpi-web.de/eccc-reports/2008/TR08-022/index.html http://eccc.hpi-web.de/eccc-reports/2008/TR08-022/index.html]<br />
}}<br />
<br />
<span id="bhr00" style="color:maroon">[BHR00]</span><br />
B. Borchert, L. Hemaspaandra, and J. Rothe.<br />
Restrictive Acceptance Suffices for Equivalence Problems.<br />
LMS J. Comput. Math. 3 (2000), 86--95<br />
arXiv:[http://arxiv.org/cs.CC/9907041 cs.CC/9907041].<br />
<br />
<span id="bhw89" style="color:maroon">[BHW89]</span><br />
R. Beigel, L. Hemachandra, and G. Wechsung.<br />
On the power of probabilistic polynomial time,<br />
<i>Proceedings of IEEE Complexity'89</i>, pp. 225-230, 1989.<br />
<br />
<span id="bhz87" style="color:maroon">[BHZ87]</span><br />
R. B. Boppana, J. H&aring;stad, and S. Zachos.<br />
Does co-NP have short interactive proofs?,<br />
<i>Information Processing Letters</i> 25:127-132, 1987.<br />
<br />
<span id="bk89" style="color:maroon">[BK89]</span><br />
M. Blum and S. Kannan.<br />
Designing programs that check their work,<br />
<i>Proceedings of ACM STOC'89</i>, 1989.<br />
<br />
<span id="bkl00" style="color:maroon">[BKL+00]</span><br />
D. A. M. Barrington, P. Kadau, K.-J. Lange, and P. McKenzie.<br />
On the complexity of some problems on groups input as multiplication tables,<br />
[http://www-fs.informatik.uni-tuebingen.de/~lange/Arbeiten/fologlog/bklm/neu.ps.gz http://www-fs.informatik.uni-tuebingen.de/~lange/Arbeiten/fologlog/bklm/neu.ps.gz]<br />
<i>Proceedings of IEEE Complexity'2000</i>, 2000.<br />
<br />
<span id="bks95" style="color:maroon">[BKS95]</span><br />
R. Beigel, M. Kummer, and F. Stephan.<br />
Approximable sets,<br />
<i>Information and Computation</i> 120(2):304-314, 1995.<br />
[http://www.cis.temple.edu/~beigel/papers/bks-queries2-ic.PS.gz http://www.cis.temple.edu/~beigel/papers/bks-queries2-ic.PS.gz].<br />
<br />
<span id="blm98" style="color:maroon">[BLM+98]</span><br />
D. A. M. Barrington, C.-J. Lu, P. B. Miltersen, and S. Skyum.<br />
Searching constant width mazes captures the AC<sup>0</sup> hierarchy,<br />
<i>Proceedings of the 1998 Symposium of Theoretical Aspects of Computer Science (STACS'98)</i>, 1998.<br />
ECCC [http://eccc.uni-trier.de/eccc-reports/1997/TR97-044/ TR97-044].<br />
<br />
<span id="blm99" style="color:maroon">[BLM+99]</span><br />
D. A. M. Barrington, C.-J. Lu, P. B. Miltersen, and S. Skyum.<br />
On monotone planar circuits,<br />
<i>Proceedings of IEEE Complexity'99</i>, 1999.<br />
[http://www.brics.dk/~bromille/Papers/mpc.ps http://www.brics.dk/~bromille/Papers/mpc.ps]<br />
<br />
<span id="bls84" style="color:maroon">[BLS84]</span><br />
R. Book, T. Long, and A. Selman.<br />
Quantitative relativizations of complexity classes,<br />
<i>SIAM Journal on Computing</i> 13(3):461-487, 1984.<br />
<br />
<span id="blu67" style="color:maroon">[Blu67]</span><br />
M. Blum. A Machine-Independent Theory of the Complexity of Recursive Functions. <i>J. ACM</i> 14: 322-336, 1967. <br />
<br />
<span id="bm04" style="color:maroon">[BM04]</span><br />
J. Buresh-Oppenheim and T. Morioka.<br />
Relativized NP search problems and propositional proof systems,<br />
<i>Proceedings of IEEE Complexity 2004</i>, pp. 54-67, 2004.<br />
ECCC [http://eccc.uni-trier.de/eccc-reports/2003/TR03-084/ TR03-084].<br />
<br />
<span id="bm88" style="color:maroon">[BM88]</span><br />
L. Babai and S. Moran.<br />
Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity classes,<br />
<i>Journal of Computer and Systems Sciences</i> 36:254-276, 1988.<br />
<br />
<span id="boo72" style="color:maroon">[Boo72]</span><br />
R. Book.<br />
On languages accepted in polynomial time,<br />
<i>SIAM Journal on Computing</i> 1(4):281-287, 1972.<br />
<br />
<span id="boo74" style="color:maroon">[Boo74]</span><br />
R. Book.<br />
Comparing complexity classes,<br />
<i>Journal of Computer and System Sciences</i> 3(9):213-229, 1974.<br />
<br />
<span id="boo94" style="color:maroon">[Boo94]</span><br />
R. Book.<br />
On collapsing the polynomial-time hierarchy,<br />
<i>Information Processing Letters</i> 52(5):235-237, 1994.<br />
<br />
<span id="bor77" style="color:maroon">[Bor77]</span><br />
A. Borodin.<br />
On relating time and space to size and depth,<br />
<i>SIAM Journal on Computing</i> 6:733-744, 1977.<br />
<br />
<span id="bra77" style="color:maroon">[Bra77]</span><br />
F.-J. Brandenburg.<br />
On one-way auxiliary pushdown automata,<br />
<i>Proceedings of the Third GI-Conference on Theoretical Computer Science</i>, Springer LNCS vol. 48, pp. 132-144, 1977.<br />
<br />
<span id="bra79" style="color:maroon">[Bra79]</span><br />
G. Brassard.<br />
A note on the complexity of cryptography<br />
<i>IEEE Transactions on Information Theory</i>, 25(2):232-233, 1979.<br />
<br />
<span id="bra06" style="color:maroon">[Bra06]</span><br />
S. Bravyi.<br />
Efficient algorithm for a quantum analogue of 2-SAT,<br />
arXiv:[http://arxiv.org/abs/quant-ph/0602108v1 quant-ph/0602108v1], 2006.<br />
<br />
<span id="brs91" style="color:maroon">[BRS91]</span><br />
R. Beigel, N. Reingold, and D. A. Spielman.<br />
PP is closed under intersection,<br />
<i>Proceedings of ACM STOC'91</i>, pp. 1-9, 1991.<br />
[http://www.cis.temple.edu/~beigel/papers/brs-pp-jcss.PS.gz http://www.cis.temple.edu/~beigel/papers/brs-pp-jcss.PS.gz].<br />
<br />
<span id="bru90" style="color:maroon">[Bru90]</span><br />
J. Bruck.<br />
Harmonic analysis of polynomial threshold functions,<br />
SIAM J. Discrete Math., 3 (1990) 168-177.<br />
<br />
<span id="bs00" style="color:maroon">[BS00]</span><br />
B. Borchert and F. Stephan.<br />
Looking for an Analogue of Rice's Theorem in Circuit Complexity Theory.<br />
MLQ Math. Log. Q. 46 (2000), no. 4, 489--504<br />
[http://math.uni-heidelberg.de/logic/bb/papers/Rice.ps http://math.uni-heidelberg.de/logic/bb/papers/Rice.ps]<br />
<br />
<span id="bs90" style="color:maroon">[BS90]</span><br />
J. Bruck and R. Smolensky.<br />
Polynomial threshold functions, AC<sup>0</sup> functions and spectral norms,<br />
<i>Proceedings of IEEE FOCS'90</i>, pp. 632-641, 1990.<br />
<br />
<span id="bs90b" style="color:maroon">[BS90b]</span><br />
R. B. Boppana and M. Sipser. The complexity of finite functions. <br />
chapter in <i>Handbook of Theoretical Computer Science</i>, Volume A (J. van Leeuwen, editor), Elsevier, 1990.<br />
<br />
<span id="bsf02" style="color:maroon">[BSF02]</span><br />
A. Ben-Hur, H. T. Siegelmann, and S. Fishman.<br />
A theory of complexity for continuous time systems,<br />
<i>Journal of Complexity</i> 18(1):51-86, 2002.<br />
[http://cmgm.stanford.edu/~asab/Papers/dds2.ps.gz http://cmgm.stanford.edu/~asab/Papers/dds2.ps.gz]<br />
<br />
<span id="bt04" style="color:maroon">[BT04]</span><br />
H. Buhrman and L. Torenvliet.<br />
Separating complexity classes using structural properties,<br />
<i>Proceedings of IEEE Complexity 2004</i>, pp. 130-138, 2004.<br />
[http://staff.science.uva.nl/~leen/PAPERS/superrobustsets.pdf http://staff.science.uva.nl/~leen/PAPERS/superrobustsets.pdf]<br />
<br />
{{Reference<br />
|tag=BT06<br />
|authors=A. Bogdanov and L. Trevisan<br />
|title=Average-Case Complexity<br />
|journal=ECCC Report TR06-073<br />
|srcdetail=Revision 01, accepted on Fri Sep 29 22:13:11 2006<br />
}}<br />
<br />
<span id="bt88" style="color:maroon">[BT88]</span><br />
D. A. M. Barrington and D. Th&eacute;rien.<br />
Finite monoids and the fine structure of NC<sup>1</sup>,<br />
<i>Journal of the ACM</i> 35(4):941-952, 1988.<br />
<br />
<span id="bur00" style="color:maroon">[Bur00]</span><br />
P. B&uuml;rgisser.<br />
<i>Completeness and Reduction in Algebraic Complexity Theory</i>,<br />
Springer Series in Algorithms and Computation in Mathematics, Volume 7, 2000.<br />
<br />
{{Reference<br />
|tag=Buss93<br />
|authors = Buss, Samuel R.<br />
|title = Algorithms for Boolean formula evaluation and for tree-contraction<br />
|journal=Proof Theory, Complexity, and Arithmetic, P. Clote and J. Krajicek (eds) <br />
|srcdetail=Oxford University Press, 1993, pp. 95-115<br />
|link=http://math.ucsd.edu/~sbuss/ResearchWeb/Boolean3/index.html<br />
}}<br />
<br />
<span id="bv97" style="color:maroon">[BV97]</span><br />
E. Bernstein and U. Vazirani.<br />
Quantum complexity theory,<br />
<i>SIAM Journal on Computing</i>, 26(5):1411-1473, 1997.<br />
[http://www.cs.berkeley.edu/~vazirani/bv.ps http://www.cs.berkeley.edu/~vazirani/bv.ps]<br />
<br />
<span id="bvw98" style="color:maroon">[BVW98]</span><br />
R. Book, H. Vollmer, and K. W. Wagner.<br />
Probabilistic type-2 operators and "almost"-classes,<br />
<i>Computational Complexity</i> 7(3):265-289, 1998.<br />
<br />
<span id="bvw07" style="color:maroon">[BVW07]</span><br />
H. Burhman, N. Vereshchajin, R. de Wolf.<br />
On computation and communication with small bias.<br />
<i>Proceedings of IEEE Conference on Computational Complexity 2007</i> 24-32, 2007.<br />
<br />
<span id="bw03" style="color:maroon">[BW03]</span><br />
H. Buhrman and R. de Wolf.<br />
Quantum Zero-Error Algorithms Cannot be Composed,<br />
Information Processing Letters, 87(2):79-84, 2003.<br />
arXiv:[http://arxiv.org/abs/quant-ph/0211029 quant-ph/0211029].<br />
<br />
===== C =====<br />
<br />
<span id="cai01" style="color:maroon">[Cai01]</span><br />
J.-Y. Cai.<br />
S<sub>2</sub>P is contained in ZPP<sup>NP</sup>,<br />
<i>Proceedings of IEEE FOCS'2001</i>, pp. 620-629, 2001.<br />
<br />
<span id="cai86" style="color:maroon">[Cai86]</span><br />
J.-Y. Cai.<br />
With probability one, a random oracle separates PSPACE from the polynomial hierarchy,<br />
<i>Proceedings of ACM STOC'86</i>, pp. 21-29, 1986.<br />
<br />
<span id="cai87" style="color:maroon">[Cai87]</span><br />
J. Cai.<br />
Probability one separation of the Boolean hieararchy,<br />
Lecture Notes in Computer Science, vol 247, p148-158, 1987.<br />
<br />
<span id="can96" style="color:maroon">[Can96]</span><br />
R. Canetti.<br />
More on BPP and the polynomial-time hierarchy,<br />
<i>Information Processing Letters</i> 57:237-241, 1996.<br />
<br />
<span id="cc93" style="color:maroon">[CC93]</span><br />
L. Cai and J. Chen.<br />
On fixed-parameter tractability and approximability of NP-hard optimization problems,<br />
<i>Proceedings of ISTCS'93 - Israel Symposium on Theory of Computing and Systems</i>, pp. 118-126, 1993.<br />
<br />
<span id="cc97" style="color:maroon">[CC97]</span><br />
L. Cai and J. Chen.<br />
On fixed-parameter tractability and approximability of NP optimization problems,<br />
<i>Journal of Computer and System Sciences</i> 54(3):465-474, 1997.<br />
<br />
<span id="ccd03" style="color:maroon">[CCD+03]</span><br />
A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D. A. Spielman.<br />
Exponential algorithmic speedup by quantum walk,<br />
<i>Proceedings of ACM Symposium on Theory of Computing</i>, pp. 59-68, 2003.<br />
arXiv:[http://arxiv.org/abs/quant-ph/0209131 quant-ph/0209131].<br />
<br />
<span id="ccg94" style="color:maroon">[CCG+94]</span><br />
R. Chang, B. Chor, O. Goldreich, J. Hartmanis, J. H&aring;stad, D. Ranjan, and P. Rohatgi.<br />
The random oracle hypothesis is false,<br />
<i>Journal of Computer and System Sciences</i> 49(1):24-39, 1994.<br />
<br />
<span id="cch01" style="color:maroon">[CCH+01]</span><br />
J.-Y. Cai, V. Chakaravarthy, L. Hemaspaandra, and M. Ogihara.<br />
Some Karp-Lipton-type theorems based on S<sub>2</sub>,<br />
University of Rochester Computer Science Technical Report TR-759, November 2001.<br />
<br />
<span id="cd05" style="color:maroon">[CD05]</span><br />
X. Chen and X. Deng<br />
3-NASH is PPAD-Complete, online: [http://eccc.uni-trier.de/eccc-reports/2005/TR05-134/Paper.pdf http://eccc.uni-trier.de/eccc-reports/2005/TR05-134/Paper.pdf], nov. 2005.<br />
<br />
<span id="cdl01" style="color:maroon">[CDL01]</span><br />
A. Chiu, G. Davida, and B. Litow.<br />
Division in logspace-uniform NC<sub>1</sub>,<br />
<i>Theoretical Informatics and Applications</i> 35(3):259, 2001.<br />
<br />
<span id="cf91" style="color:maroon">[CF91]</span><br />
J.-Y. Cai and M. Furst.<br />
PSPACE survives constant-width bottlenecks,<br />
<i>International Journal of Foundations of Computer Science</i> 2(1):67-76, 1991.<br />
<br />
{{Reference<br />
|id=cf07 |tag=CP07<br />
|title=On parameterized path and chordless path problems<br />
|authors=Y. Chen and J. Flum<br />
|journal=Proceedings of the IEEE Conference on Computational Complexity 2007<br />
|srcdetail=250-263<br />
}}<br />
<br />
{{Reference<br />
|tag=CFL83<br />
|title=Unbounded fan-in circuits and associative functions<br />
|authors=A. Chandra, S. Fortune, R. Lipton<br />
|journal=Proceedings of the fifteenth annual ACM symposium on Theory of computing<br />
|srcdetail=52-60, 1983<br />
}}<br />
<br />
<span id="cfl93" style="color:maroon">[CFL+93]</span><br />
A. Condon, J. Feigenbaum, C. Lund, and P. Shor.<br />
Probabilistically checkable debate systems and approximation algorithms for PSPACE-hard functions (extended abstract),<br />
<i>Proceedings of ACM STOC'93</i>, pp. 305-314, 1993.<br />
<br />
<span id="cgh88" style="color:maroon">[CGH+88]</span><br />
J.-Y. Cai, T. Gundermann, J. Hartmanis, L. Hemachandra, V. Sewelson, K. Wagner, and G. Wechsung.<br />
The Boolean hierarchy I: structural properties,<br />
<i>SIAM Journal on Computing</i> 17:1232-1252, 1988.<br />
Part II: applications in 18:95-111, 1989.<br />
<br />
<span id="cgr04" style="color:maroon">[CGR+04]</span><br />
M. Crasmaru, C. Gla&szlig;er, K. W. Regan, and S. Sengupta.<br />
A protocol for serializing unique strategies,<br />
submitted, 2004.<br />
[http://www.cse.buffalo.edu/faculty/regan/papers/ps/CGRS03.ps http://www.cse.buffalo.edu/faculty/regan/papers/ps/CGRS03.ps].<br />
<br />
<span id="ch89" style="color:maroon">[CH89]</span><br />
J.-Y. Cai and L. A. Hemachandra.<br />
On the power of parity polynomial time,<br />
<i>Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS)</i>, Lecture Notes in Computer Science 349, pp. 229-240, Springer, 1989.<br />
<br />
<span id="cht04" style="color:maroon">[CHT+04]</span><br />
R. Cleve, P. H&oslash;yer, B. Toner, and J. Watrous.<br />
Consequences and limits of nonlocal strategies,<br />
<i>Proceedings of IEEE Complexity</i>, pp. 236-249, 2004.<br />
arXiv:[http://arxiv.org/abs/quant-ph/0404076 quant-ph/0404076].<br />
<br />
<span id="chu41" style="color:maroon">[Chu41]</span><br />
A. Church.<br />
The calculi of lambda-conversion,<br />
<i>Annals of Mathematical Studies</i> 6, Princeton Univ. Press, 1941.<br />
<br />
{{Reference<br />
|tag=CIK+03<br />
|title=The complexity of Unique <math>k</math>-SAT: An isolation lemma for <math>k</math>-CNFs.<br />
|authors=C. Calabro, R. Impagliazzo, V. Kabanets, et al<br />
|journal=Proceedings of the IEEE Conference on Computational Complexity 2003<br />
|srcdetail=135-141<br />
}}<br />
<br />
<span id="ckk95" style="color:maroon">[CKK+95]</span><br />
F. Cucker, M. Karpinski, P. Koiran, T. Lickteig, and K. Werther.<br />
On real Turing machines that toss coins,<br />
<i>Proceedings of ACM STOC'95</i>, pp. 335-342, 1995.<br />
<br />
<span id="cks81" style="color:maroon">[CKS81]</span><br />
A. K. Chandra, D. C. Kozen, and L. J. Stockmeyer.<br />
Alternation,<br />
<i>Journal of the ACM</i> 28:114-133, 1981.<br />
<br />
<span id="cks99" style="color:maroon">[CKS+99]</span><br />
P. Crescenzi, V. Kann, R. Silvestri, and L. Trevisan.<br />
Structure in approximation classes,<br />
<i>SIAM Journal on Computing</i> 28:1759-1782, 1999.<br />
ECCC [http://eccc.uni-trier.de/eccc-reports/1996/TR96-066/ TR96-066].<br />
<br />
<span id="cksu05" style="color:maroon">[CKSU05]</span><br />
H. Cohn, R. Kleinberg, B. Szegedy, and C. Umans. Group-theoretic Algorithms for Matrix Multiplication. <i>Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS)</i> 379-388, 2005.<br />
<br />
<span id="cm01" style="color:maroon">[CM01]</span><br />
M. Cryan and P. B. Miltersen.<br />
On pseudorandom generators in NC<sup>0</sup>,<br />
<i>Proceedings of the 26th International Symposium on Mathematical Foundations of Computer Science (MFCS)</i>, pp. 272-284, 2001.<br />
<br />
{{Reference<br />
|tag=CMTV98<br />
|title=Nondeterministic NC1 computation<br />
|authors=Caussinus, Herv&eacute; and McKenzie, Pierre and Th&eacute;rien, Denis and Vollmer, Heribert<br />
|journal=J. Comput. Syst. Sci.<br />
|srcdetail=200-212, 1998<br />
}}<br />
<br />
<span id="cmi00" style="color:maroon">[CMI00]</span><br />
Clay Mathematics Institute.<br />
The P versus NP problem (a millennium prize problem), with official problem description by S. Cook,<br />
[http://www.claymath.org/prizeproblems/pvsnp.htm http://www.claymath.org/prizeproblems/pvsnp.htm], 2000.<br />
<br />
<span id="cns99" style="color:maroon">[CNS99]</span><br />
J.-Y. Cai, A. P. Nerurkar, and D. Sivakumar.<br />
Hardness and hierarchy theorems for probabilistic quasi-polynomial time,<br />
<i>Proceedings of ACM STOC'99</i>, pp. 726-735, 1999.<br />
<br />
<span id="cob64" style="color:maroon">[Cob64]</span><br />
A. Cobham.<br />
The intrinsic computational difficulty of functions,<br />
<i>Proceedings of the 1964 Congress on Logic, Mathematics and the Methodology of Science</i>, pp. 24-30, 1964.<br />
<br />
<span id="cob66" style="color:maroon">[Cob66]</span><br />
A. Cobham.<br />
The recognition problem for the set of perfect squares,<br />
<i>Proceedings of the 7th Symposium on Switching and Automata Theory</i>, pp. 78-87, 1966.<br />
<br />
<span id="con73" style="color:maroon">[Con73]</span><br />
R. Constable.<br />
Type 2 computational complexity,<br />
<i>Proceedings of ACM STOC'73</i>, pp. 108-121, 1973.<br />
<br />
<span id="con92" style="color:maroon">[Con92]</span><br />
A. Condon.<br />
The complexity of stochastic games,<br />
<i>Information and Computation</i> 96(2):203-224, 1992.<br />
<br />
<span id="coo71" style="color:maroon">[Coo71]</span><br />
S. A. Cook.<br />
The complexity of theorem-proving procedures,<br />
<i>Proceedings of ACM STOC'71</i>, pp. 151-158, 1971.<br />
<br />
<span id="coo71b" style="color:maroon">[Coo71b]</span><br />
S. A. Cook.<br />
Characterizations of pushdown machines in terms of time-bounded computers,<br />
<i>Journal of the ACM</i> 18(1):4-18, 1971.<br />
<br />
<span id="coo79" style="color:maroon">[Coo79]</span><br />
S. A. Cook.<br />
Deterministic CFL's are accepted simultaneously in polynomial time and log squared space,<br />
<i>Proceedings of ACM STOC'79</i>, pp. 338-345, 1979.<br />
<br />
<span id="coo85" style="color:maroon">[Coo85]</span><br />
S. A. Cook.<br />
A taxonomy of problems with fast parallel algorithms,<br />
<i>Information and Control</i> 64:2-22, 1985.<br />
<br />
<span id="cp95" style="color:maroon">[CP95]</span><br />
P. Crescenzi and C. Papadimitriou.<br />
Reversible simulation of space-bounded computations,<br />
<i>Theoretical Computer Science</i> 143:159-165, 1995.<br />
<br />
{{Reference<br />
|id=cp07 |tag=CP07<br />
|title=Bounded queries and the NP Machine Hypothesis.<br />
|authors=R. Chang and S. Purini<br />
|journal=Proceedings of the IEEE Conference on Computational Complexity 2007<br />
|srcdetail=52-59<br />
}}<br />
<br />
<span id="cr96" style="color:maroon">[CR96]</span><br />
S. Chaudhuri and J. Radhakrishnan. <br />
Deterministic Restrictions in Circuit Complexity, <br />
<i>Proceedings of ACM STOC 1996</i>, pp. 30-36, 1996.<br />
<br />
<span id="cs92" style="color:maroon">[CS92]</span><br />
J. Castro and C. Seara.<br />
Characterizations of some complexity classes between &#920;<sub>2</sub><sup>p</sup> and &#916;<sub>2</sub><sup>p</sup>,<br />
<i>Proceedings of STACS 1992</i>, pp. 305-317, 1992.<br />
<br />
<span id="ct94" style="color:maroon">[CT94]</span><br />
P. Crescenzi and L. Trevisan.<br />
An approximation scheme preserving reducibility and its applications,<br />
<i>Proceedings of 14th Annual Conference on Foundations of Software Technology and Theoretical Computer Computer Science (FSTTCS)</i>, pp. 330-341, Lecture Notes in Computer Science 880, Springer-Verlag, 1994.<br />
<br />
<span id="ct97" style="color:maroon">[CT97]</span><br />
M. Cesati and L. Trevisan.<br />
On the efficiency of polynomial time approximation schemes,<br />
ECCC [http://eccc.uni-trier.de/eccc-reports/1997/TR97-001/ TR97-001], 1997.<br />
<br />
<span id="ct07" style="color:maroon">[CT07]</span><br />
Xi Chen and Shang-Hua Teng.<br />
Paths beyond local search: A nearly tight bound for randomized fixed-point computation.<br />
FOCS 2007.<br />
<br />
<span id="cw82" style="color:maroon">[CW82]</span> D. Coppersmith and S. Winograd. On the Asymptotic Complexity of Matrix Multiplication. <i>SIAM J. Comput.</i> 11(3): 472-492,1982.<br />
<br />
{{Reference<br />
|tag=CW90<br />
|title=Matrix multiplication via arithmetic progressions<br />
|journal=Journal of Symbolic Computation<br />
|srcdetail=9:251–280, 1990<br />
|authors=D. Coppersmith and S. Winograd<br />
}}<br />
<br />
<span id="cw00" style="color:maroon">[CW00]</span><br />
R. Cleve and J. Watrous.<br />
Fast parallel circuits for the quantum Fourier transform,<br />
<i>Proceedings of IEEE Focs'2000</i>, pp. 526-536, 2000.<br />
arXiv:[http://arxiv.org/abs/quant-ph/0006004 quant-ph/0006004].<br />
<br />
===== D =====<br />
<br />
<span id="dam90" style="color:maroon">[Dam90]</span><br />
C. Damm.<br />
Problems complete for L,<br />
<i>Information Processing Letters</i> 36:247-250, 1990.<br />
<br />
<span id="dc89" style="color:maroon">[DC89]</span><br />
P. W. Dymond and S. Cook.<br />
Complexity theory of parallel time and hardware,<br />
<i>Information and Computation</i> 80:205-226, 1989.<br />
<br />
<span id="ddp98" style="color:maroon">[DDP+98]</span><br />
A. De Santis, G. Di Crescenzo, G. Persiano, and M. Yung.<br />
Image density is complete for non-interactive SZK,<br />
<i>Proceedings of the 25th International Colloquium on Automata, Languages, and Programming (ICALP)</i>, Lecture Notes in Computer Science, pp. 784-795, 1998.<br />
(Note: Some results in the paper were later retracted.)<br />
<br />
<span id="dek76" style="color:maroon">[Dek76]</span><br />
M. I. Dekhtyar.<br />
On the relativization of deterministic and nondeterministic complexity classes,<br />
<i>Mathematical Foundations of Computer Science</i>, pp. 255-259, Springer LNCS 45, 1976.<br />
<br />
<span id="df97" style="color:maroon">[DF97]</span><br />
R. G. Downey and M. R. Fellows.<br />
Threshold dominating sets and an improved characterization of W[2],<br />
<i>Theoretical Computer Science</i> 189, 1997.<br />
<br />
<span id="df99" style="color:maroon">[DF99]</span><br />
R. G. Downey and M. R. Fellows.<br />
<i>Parameterized Complexity</i>,<br />
Springer-Verlag Monographs in Computer Science, 1999.<br />
<br />
<span id="dft96" style="color:maroon">[DFT96]</span><br />
R. G. Downey, M. R. Fellows, and U. Taylor.<br />
On the parameteric complexity of relational database queries and a sharper characterization of W[1],<br />
<i>Combinatorics, Complexity, and Logic</i>, Proceedings of DMTCS'96, Springer-Verlag, pp. 194-213, 1996.<br />
<br />
<span id="dgp05" style="color:maroon">[DGP05]</span><br />
C. Daskalakis, P. W. Goldberg, and C. H. Papadimitriou<br />
The Complexity of Computing a Nash Equilibrium, online: [http://www.cs.berkeley.edu/~christos/papers/ppad.ps ppad.ps], sep. 2005.<br />
<br />
<span id="dhi02" style="color:maroon">[DHI02]</span><br />
W. van Dam, S. Hallgren, and L. Ip.<br />
Quantum algorithms for hidden shift problems,<br />
arXiv:[http://arxiv.org/abs/quant-ph/0211140 quant-ph/0211140], 2002.<br />
<br />
<span id="dp05" style="color:maroon">[DP05]</span><br />
C. Daskalakis and C. H. Papadimitriou<br />
The Complexity of Computing a Nash Equilibrium, online: [http://www.cs.berkeley.edu/~christos/papers/3players.pdf 3players.pdf], nov. 2005.<br />
<br />
{{Reference-ECCC<br />
|tag=DP08 |year=2008 |date=Feb 28 |eccc-num=TR08-014<br />
|authors=M. David and T. Pitassi<br />
|title=Separating NOF communication complexity classes RP and NP<br />
}}<br />
<br />
<span id="dw86" style="color:maroon">[DW86]</span><br />
E. Dahlhaus and M. K. Warmuth.<br />
Membership for growing context-sensitive grammars is polynomial,<br />
<i>Journal of Computer and System Sciences</i> 33:456-472, 1986.<br />
<br />
===== E =====<br />
<br />
<span id="edm65" style="color:maroon">[Edm65]</span><br />
J. Edmonds.<br />
Paths, trees, and flowers,<br />
<i>Canadian Journal of Mathematics</i> 17(3):449-467, 1965.<br />
<br />
<span id="ey07" style="color:maroon">[EY07]</span><br />
K. Etessami and M. Yannakakis.<br />
On the Complexity of Nash Equilibria and Other Fixed Points.<br />
Unpublished.<br />
<br />
Paths, trees, and flowers,<br />
<i>Canadian Journal of Mathematics</i> 17(3):449-467, 1965.<br />
<br />
===== F =====<br />
<br />
<span id="fag73" style="color:maroon">[Fag73]</span><br />
R. Fagin.<br />
Contributions to the Model Theory of Finite Strucutres,<br />
<i>Ph.D. Thesis (1973), U.C. Berkeley</i><br />
<br />
<span id="fag74" style="color:maroon">[Fag74]</span><br />
R. Fagin.<br />
Generalized first-order spectra and polynomial-time recognizable sets,<br />
<i>Complexity of Computation</i> (R. M. Karp, ed.), SIAM-AMS Proceedings Vol. 7, 1974.<br />
<br />
<span id="fen02" style="color:maroon">[Fen02]</span><br />
S. Fenner.<br />
PP-lowness and a simple definition of AWPP,<br />
<i>Theory Comput. Syst.</i> 36 (2003), no. 2, 199--212.<br />
ECCC [http://eccc.uni-trier.de/eccc-reports/2002/TR02-036/ TR02-036].<br />
<br />
<span id="ff.." style="color:maroon">[FF..]</span><br />
S. Fenner, L. Fortnow,<br />
Unpublished.<br />
<br />
<span id="ffk93" style="color:maroon">[FFK+93]</span><br />
S. Fenner, L. Fortnow, S. Kurtz, and L. Li.<br />
An oracle builder's toolkit,<br />
<i>Proceedings of Structure in Complexity Theory</i>, pages 120-131, 1993.<br />
[http://people.cs.uchicago.edu/~fortnow/papers/obt.ps http://people.cs.uchicago.edu/~fortnow/papers/obt.ps].<br />
<br />
<span id="ffk94" style="color:maroon">[FFK94]</span><br />
S. Fenner, L. Fortnow, and S. Kurtz.<br />
Gap-definable counting classes,<br />
<i>Journal of Computer and System Sciences</i> 48(1):116-148, 1994.<br />
[http://people.cs.uchicago.edu/~fortnow/papers/gaps.ps http://people.cs.uchicago.edu/~fortnow/papers/gaps.ps].<br />
<br />
<span id="fg02" style="color:maroon">[FG02]</span><br />
J. Flum and M. Grohe.<br />
The parameterized complexity of counting problems,<br />
<i>Proceedings of IEEE FOCS'2002</i>, 2002.<br />
<br />
<span id="fgh98" style="color:maroon">[FGH+98]</span><br />
S. Fenner, F. Green, S. Homer, and R. Pruim.<br />
Quantum NP is hard for PH,<br />
<i>Proceedings of the Sixth Italian Conference on Theoretical Computer Science</i>, World-Scientific, pp. 241-252, 1998.<br />
arXiv:[http://arxiv.org/abs/quant-ph/9812056 quant-ph/9812056].<br />
<br />
<span id="fgl91" style="color:maroon">[FGL+91]</span><br />
U. Feige, S. Goldwasser, L. Lov&aacute;sz, S. Safra, and M. Szegedy.<br />
Approximating clique is almost NP-complete,<br />
<i>Proceedings of IEEE FOCS'91</i>, pp. 2-12, 1991.<br />
<br />
<span id="fgmsz89" style="color:maroon">[FGM+89]</span><br />
M. Furer, O. Goldreich, Y. Mansour, M. Sipser, and S. Zachos.<br />
On Completeness and Soundness in Interactive Proof Systems.<br />
In <i>Advances in Computing Research: a research annual</i>,<br />
Vol.~5 (Randomness and Computation, S. Micali, ed.),<br />
pages 429--442, 1989.<br />
<br />
<span id="fie98" style="color:maroon">[Fie98]</span><br />
U. Feige.<br />
A threshold of ln(n) for approximating set cover.<br />
<i>Journal of the ACM (JACM)</i>, 45(4): 634--652, 1998.<br />
[http://dx.doi.org/10.1145/285055.285059 doi:10.1145/285055.285059]<br />
<br />
<span id="fk05" style="color:maroon">[FK05]</span><br />
L. Fortnow and A. Klivans.<br />
NP with small advice,<br />
<i>Proceedings of IEEE Complexity'2005</i>, pp. 228-234, 2005.<br />
[http://people.cs.uchicago.edu/~fortnow/papers/fk.ps http://people.cs.uchicago.edu/~fortnow/papers/fk.ps].<br />
<br />
<span id="fk97" style="color:maroon">[FK97]</span><br />
U. Feige and J. Kilian.<br />
Limited versus polynomial nondeterminism,<br />
<i>Chicago Journal of Theoretical Computer Science</i> Article 1, 1997.<br />
<br />
<span id="fk97b" style="color:maroon">[FK97b]</span><br />
U. Feige and J. Kilian.<br />
Making games short,<br />
<i>Proceedings of ACM STOC'1997</i>, pp. 506-516, 1997.<br />
<br />
<span id="for94" style="color:maroon">[For94]</span><br />
L. Fortnow.<br />
The role of relativization in complexity theory,<br />
<i>Bulletin of the EATCS</i> 52, February 1994.<br />
[http://people.cs.uchicago.edu/~fortnow/papers/relative.ps http://people.cs.uchicago.edu/~fortnow/papers/relative.ps].<br />
<br />
<span id="fr74" style="color:maroon">[FR74]</span><br />
M. J. Fischer and M. O. Rabin.<br />
Super-exponential complexity of Presburger arithmetic,<br />
<i>Complexity of Computation</i> (R. M. Karp, ed.), SIAM-AMS Symposium on Applied Mathematics, 1974.<br />
<br />
<span id="fr98" style="color:maroon">[FR98]</span><br />
L. Fortnow and J. D. Rogers.<br />
Complexity limitations on quantum computation,<br />
<i>Proceedings of IEEE Complexity'98</i>, pp. 202-209, 1998.<br />
arXiv:[http://arxiv.org/abs/cs.CC/9811023 cs.CC/9811023].<br />
<br />
<span id="fri57" style="color:maroon">[Fri57]</span><br />
R. M. Friedberg.<br />
Two recursively enumerable sets of incomparable degrees of unsolvability,<br />
<i>Proceedings of the National Academy of Sciences</i>, 43:236-238, 1957.<br />
[http://www.pubmedcentral.nih.gov/picrender.fcgi?artid=528418&amp;blobtype=pdf http://www.pubmedcentral.nih.gov/picrender.fcgi?artid=528418&amp;blobtype=pdf].<br />
<br />
<span id="frs88" style="color:maroon">[FRS88]</span><br />
L. Fortnow, J. Rompel, and M. Sipser.<br />
On the power of multiprover interactive protocols,<br />
<i>Proceedings of IEEE Complexity'88</i>, 1988.<br />
[http://people.cs.uchicago.edu/~fortnow/papers/mip.ps http://people.cs.uchicago.edu/~fortnow/papers/mip.ps].<br />
<br />
<span id="fs04" style="color:maroon">[FS04]</span><br />
L. Fortnow and R. Santhanam.<br />
Hierarchy theorems for probabilistic polynomial time,<br />
<i>Proceedings of IEEE FOCS'2004</i>, 2004.<br />
[http://people.cs.uchicago.edu/~fortnow/papers/probhier.ps http://people.cs.uchicago.edu/~fortnow/papers/probhier.ps].<br />
<br />
<span id="fs88" style="color:maroon">[FS88]</span><br />
L. Fortnow and M. Sipser.<br />
Are there interactive protocols for co-NP languages?<br />
Inform. Process. Lett. 28 (1988), no. 5, 249--251.<br />
[http://cs-www.uchicago.edu/~fortnow/papers/conpipl.ps http://cs-www.uchicago.edu/~fortnow/papers/conpipl.ps]<br />
<br />
<span id="fss84" style="color:maroon">[FSS84]</span><br />
M. Furst, J. Saxe, and M. Sipser.<br />
Parity, circuits, and the polynomial hierarchy,<br />
<i>Mathematical Systems Theory</i> 17:13-27, 1984.<br />
<br />
<span id="fur07" style="color:maroon">[Fur07]</span><br />
M. Furer.<br />
Fast Integer Multiplication,<br />
STOC, 2007.<br />
<br />
<span id="fv93" style="color:maroon">[FV93]</span><br />
T. Feder and M. Y. Vardi.<br />
Monotone monadic SNP and constraint satisfaction,<br />
<i>Proceedings of the 25th ACM Symposium on Theory of Computing</i>, pp. 612-622, 1993.<br />
DOI:[http://doi.acm.org/10.1145/167088.167245 10.1145/167088.167245].<br />
<br />
===== G =====<br />
<br />
<span id="gas02" style="color:maroon">[Gas02]</span><br />
William Gasarch.<br />
The P=?NP poll,<br />
<i>SIGACT News Complexity Theory Column 36</i> (L. A. Hemaspaandra, ed.), 2002.<br />
<br />
<span id="gas02" style="color:maroon">[Geff91]</span><br />
Viliam Geffert.<br />
Nondeterministic computations in sublogarithmic space and space constructibility,<br />
<i>SIAM Journal on Computing</i> v. 20 iss. 3, 1991.<br />
[http://portal.acm.org/citation.cfm?id=114454&dl=GUIDE&coll=GUIDE&CFID=74222314&CFTOKEN=30698817]<br />
<br />
<span id="gg66" style="color:maroon">[GG66]</span><br />
S. Ginsburg and S. Greibach.<br />
Deterministic context free languages,<br />
<i>Information and Control</i> 9:620-648, 1966.<br />
<br />
<span id="ggk03" style="color:maroon">[GGK03]</span><br />
William Gasarch, Evan Golub and Clyde Kruskal. <br />
Constant time parallel sorting: an empirical view,<br />
<i>J. Comput. Syst. Sci.</i> 67:63-91, 2003.<br />
<br />
<span id="ghj91" style="color:maroon">[GHJ+91]</span><br />
J. Goldsmith, L. A. Hemaspaandra, D. Joseph, and P. Young.<br />
Near-testable sets.<br />
SIAM J. Comput. 20 (1991), no. 3, 506--523<br />
<br />
<span id="ghp00" style="color:maroon">[GHP00]</span><br />
F. Green, S. Homer, and C. Pollett.<br />
On the complexity of quantum ACC,<br />
<i>Proceeedings of IEEE Complexity'2000</i>, pp. 250-262, 2000.<br />
See also:<br />
F. Green, S. Homer, C. Moore, and S. Pollett.<br />
Counting, fanout, and the complexity of quantum ACC,<br />
arXiv:[http://arxiv.org/abs/quant-ph/0106017 quant-ph/0106017], 2001.<br />
<br />
<span id="gil77" style="color:maroon">[Gil77]</span><br />
J. Gill.<br />
Computational complexity of probabilistic Turing machines,<br />
<i>SIAM Journal on Computing</i> 6(4):675-695, 1977.<br />
<br />
<span id="gj79" style="color:maroon">[GJ79]</span><br />
M. R. Garey and D. S. Johnson.<br />
<i>Computers and Intractability: A Guide to the Theory of NP-Completeness</i>,<br />
Freeman, 1979.<br />
<br />
<span id="gkr95" style="color:maroon">[GKR+95]</span><br />
F. Green, J. K&ouml;bler, K. W. Regan, T. Schwentick, and J. Tor&aacute;n.<br />
The power of the middle bit of a #P function,<br />
<i>Journal of Computer and System Sciences</i> 50(3):456-467, 1995.<br />
<br />
<span id="glm96" style="color:maroon">[GLM96]</span><br />
J. Goldsmith, M. A. Levy, and M. Mundhenk.<br />
Limited nondeterminism,<br />
<i>SIGACT News</i> 27(2):20-29, 1996.<br />
[http://cs.engr.uky.edu/~goldsmit/papers/extended.ps http://cs.engr.uky.edu/~goldsmit/papers/extended.ps]<br />
<br />
<span id="gmr89" style="color:maroon">[GMR89]</span><br />
S. Goldwasser, S. Micali, and C. Rackoff.<br />
The knowledge complexity of interactive proof systems,<br />
<i>SIAM Journal on Computing</i> 18(1):186-208, 1989.<br />
<br />
<span id="gmw91" style="color:maroon">[GMW91]</span><br />
O. Goldreich, S. Micali, and A. Wigderson.<br />
Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems,<br />
<i>Journal of the ACM</i> 38(1):691-729, 1991.<br />
<br />
<span id="gn13" style="color:maroon">[GN13]</span><br />
David Gosset and Daniel Nagaj.<br />
Quantum 3-SAT is QMA1-complete,<br />
arXiv:[http://arxiv.org/abs/1302.0290], 2013.<br />
<br />
{{Reference<br />
|tag=GO95<br />
|title=On a class of <math>O(n^2)</math> problems in computational geometry<br />
|authors=A. Gajentaan and M. Overmars<br />
|journal=Computational Geometry<br />
|srcdetail=Volume 5, Issue 3, October 1995, pages 165-185<br />
}}<br />
<br />
<span id="gol97" style="color:maroon">[Gol97]</span><br />
O. Goldreich.<br />
Notes on Levin's theory of average-case complexity,<br />
ECCC [http://eccc.uni-trier.de/eccc-reports/1997/TR97-058/ TR97-058].<br />
<br />
<span id="gp01" style="color:maroon">[GP01]</span><br />
F. Green and R. Pruim.<br />
Relativized separation of EQP from P^NP,<br />
Information Processing Letters 80 (2001) 257-260.<br />
[http://cs.clarku.edu/~fgreen/papers/eqp.ps http://cs.clarku.edu/~fgreen/papers/eqp.ps]<br />
<br />
<span id="gp86" style="color:maroon">[GP86]</span><br />
L. Goldschlager and I. Parberry.<br />
On the construction of parallel computers from various bases of Boolean functions,<br />
<i>Theoretical Computer Science</i> 43(1):43-58, 1986.<br />
<br />
<span id="gp91" style="color:maroon">[GP91]</span><br />
O. Goldreich and E. Petrank.<br />
Quantifying knowledge complexity,<br />
<i>Proceedings of IEEE FOCS'91</i>, pp. 59-68, 1991.<br />
[http://www.wisdom.weizmann.ac.il/~oded/PS/gp.ps http://www.wisdom.weizmann.ac.il/~oded/PS/gp.ps]<br />
<br />
<span id="gra92" style="color:maroon">[Grä92]</span><br />
E. Grädel<br />
Capturing complexity classes b fragments of second order logic<br />
<i>Information and computaiton</i> 119 (1995), 129-135<br />
<br />
<span id="gre90" style="color:maroon">[Gre90]</span><br />
F. Green.<br />
An oracle separating +P from PP<sup>PH</sup>,<br />
Inform. Process. Lett. 37 (1991), no. 3, 149--153.<br />
<br />
<span id="gre93" style="color:maroon">[Gre93]</span><br />
F. Green.<br />
On the power of deterministic reductions to C<sub>=</sub>P,<br />
Math. Systems Theory 26 (1993), no. 2, 215--233.<br />
<br />
<span id="gs86" style="color:maroon">[GS86]</span><br />
S. Goldwasser and M. Sipser.<br />
Private coins versus public coins in interactive proof systems,<br />
<i>Proceedings of ACM STOC'86</i>, pp. 58-68, 1986.<br />
<br />
<span id="gs88" style="color:maroon">[GS88]</span><br />
J. Grollman and A. L. Selman.<br />
Complexity measures for public-key cryptosystems,<br />
<i>SIAM Journal on Computing</i> 17:309-335, 1988.<br />
<br />
<span id="gs89" style="color:maroon">[GS89]</span><br />
Y. Gurevich and S. Shelah.<br />
Nearly Linear Time,<br />
<i>Proceedings of LFCS'89</i>, Springer LNCS 363, pp. 108-118, 1989.<br />
<br />
<span id="gs90" style="color:maroon">[GS90]</span><br />
M. Grigni and M. Sipser.<br />
Monotone complexity,<br />
<i>Proceedings of LMS Workshop on Boolean Function Complexity</i> (M. S. Paterson, ed.), Durham, Cambridge University Press, 1990.<br />
[http://www.mathcs.emory.edu/~mic/papers/4.ps http://www.mathcs.emory.edu/~mic/papers/4.ps]<br />
<br />
<span id="gs91" style="color:maroon">[GS91]</span><br />
M. Grigni and M. Sipser.<br />
Monotone separation of NC<sup>1</sup> from logspace,<br />
<i>Proceedings of IEEE Complexity'91</i>, pp. 294-298, 1991.<br />
<br />
<span id="gri01" style="color:maroon">[Gri01]</span><br />
Michelangelo Grigni.<br />
A Sperner lemma complete for PPA<br />
<i>Information Processing Letters</i> 77:5-6 (2001), pp. 255-259.<br />
<br />
<span id="gss03" style="color:maroon">[GSS+03]</span><br />
C. Gla&szlig;er, A. L. Selman, S. Sengupta, and L. Zhang.<br />
Disjoint NP-pairs,<br />
ECCC [http://eccc.uni-trier.de/eccc-reports/2003/TR03-011/ TR03-011], 2003.<br />
<br />
<span id="gst03" style="color:maroon">[GST03]</span><br />
D. Gutfreund, R. Shaltiel, and A. Ta-Shma.<br />
Uniform hardness vs. randomness tradeoffs for Arthur-Merlin games,<br />
<i>Comput. Complexity</i> 12 (2003), no. 3-4, 85--130.<br />
[http://www.cs.huji.ac.il/~danig/pubs/ccc.ps http://www.cs.huji.ac.il/~danig/pubs/ccc.ps].<br />
<br />
<span id="gsv99" style="color:maroon">[GSV99]</span><br />
O. Goldreich, A. Sahai, and S. Vadhan.<br />
Can statistical zero knowledge be made non-interactive? or on the relationship of SZK and NISZK,<br />
ECCC [http://eccc.uni-trier.de/eccc-reports/1999/TR99-013/ TR99-013], 1999.<br />
Abstract appeared in CRYPTO'99.<br />
<br />
<span id="gtw91" style="color:maroon">[GTW+91]</span><br />
R. Gavald&aacute;, L. Torenvliet, O. Watanabe, and J. Balc&aacute;zar.<br />
Generalized Kolmogorov complexity in relativized separations,<br />
<i>Proceedings of MFCS'91 (Mathematical Foundations of Computer Science)</i>, Springer-Verlag Lecture Notes in Computer Science, vol. 452, pp. 269-276, 1991.<br />
<br />
<span id="gup95" style="color:maroon">[Gup95]</span><br />
S. Gupta.<br />
Closure properties and witness reduction,<br />
<i>Journal of Computer and System Sciences</i> 50(3):412-432, 1995.<br />
[ftp://ftp.cis.ohio-state.edu/pub/tech-report/1993/TR46.ps.gz ftp://ftp.cis.ohio-state.edu/pub/tech-report/1993/TR46.ps.gz]<br />
<br />
<span id="gur87" style="color:maroon">[Gur87]</span><br />
Y. Gurevich.<br />
Complete and incomplete randomized NP problems,<br />
<i>Proceedings of IEEE FOCS'87</i>, pp. 111-117, 1987.<br />
<br />
<span id="gur89" style="color:maroon">[Gur89]</span><br />
E. Gurari.<br />
<i>An Introduction to the Theory of Computation</i>,<br />
Computer Science Press, 1989.<br />
[http://www.cse.ohio-state.edu/~gurari/theory-bk/theory-bk.html http://www.cse.ohio-state.edu/~gurari/theory-bk/theory-bk.html].<br />
<br />
<span id="gut05" style="color:maroon">[Gut05]</span><br />
G. Gutoski.<br />
Upper bounds for quantum interactive proofs with competing provers,<br />
<i>Proceedings of IEEE Complexity'2005</i>, pp. 334-343, 2005.<br />
[http://www.cs.uwaterloo.ca/~gmgutosk/gutoskig_competing.pdf http://www.cs.uwaterloo.ca/~gmgutosk/gutoskig_competing.pdf].<br />
<br />
<span id="gv02" style="color:maroon">[GV02]</span><br />
M. de Graaf and P. Valiant.<br />
Comparing EQP and MOD<sub>p^k</sub>P using polynomial degree lower bounds,<br />
arXiv:[http://arxiv.org/abs/quant-ph/0211179 quant-ph/0211179], 2002.<br />
<br />
<span id="gv99" style="color:maroon">[GV99]</span><br />
O. Goldreich and S. Vadhan.<br />
Comparing entropies in statistical zero-knowledge with applications to the structure of SZK,<br />
<i>Proceedings of IEEE Complexity'99</i>, pp. 54-73, 1999.<br />
ECCC [http://eccc.uni-trier.de/eccc-reports/1998/TR98-063/ TR98-063].<br />
<br />
<span id="gw05" style="color:maroon">[GW05]</span><br />
G. Gutoski and J. Watrous.<br />
Quantum interactive proofs with competing provers,<br />
<i>Proceedings of STACS'2005</i>, pp. 605-616, Springer-Verlag, 2005.<br />
arXiv:[http://arxiv.org/abs/cs.CC/0412102 cs.CC/0412102].<br />
<br />
<span id="gw07" style="color:maroon">[GW07]</span><br />
G. Gutoski and J. Watrous.<br />
Toward a general theory of quantum games,<br />
In <i>Proceedings of the 39th ACM Symposium on Theory of Computing (STOC'07)</i>, pages 565-574, 2007.<br />
arXiv:[http://arxiv.org/abs/quant-ph/0611234 quant-ph/0611234].<br />
<br />
<span id="gw10" style="color:maroon">[GW10]</span><br />
G. Gutoski and X. Wu.<br />
Short quantum games characterize PSPACE,<br />
2010.<br />
arXiv:[http://arxiv.org/abs/1011.2787 arXiv:1011.2787].<br />
<br />
<span id="gw96" style="color:maroon">[GW96]</span><br />
A. G&aacute;l and A. Wigderson.<br />
Boolean complexity classes vs. their arithmetic analogs,<br />
<i>Random Structures and Algorithms</i> 9:1-13, 1996.<br />
ECCC [http://eccc.uni-trier.de/eccc-reports/1995/TR95-049/ TR95-049].<br />
<br />
<span id="gz97" style="color:maroon">[GZ97]</span><br />
O. Goldreich and D. Zuckerman.<br />
Another proof that BPP subseteq PH (and more),<br />
ECCC [http://eccc.uni-trier.de/eccc-reports/1997/TR97-045/ TR97-045].<br />
<br />
===== H =====<br />
<br />
<span id="hal02" style="color:maroon">[Hal02]</span><br />
S. Hallgren.<br />
Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem,<br />
<i>Proceedings of ACM STOC'2002</i>, 2002.<br />
[http://www.cse.psu.edu/~hallgren/pell.pdf http://www.cse.psu.edu/~hallgren/pell.pdf].<br />
<br />
<span id="har78" style="color:maroon">[Har78]</span><br />
J. Hartmanis.<br />
<i>Feasible Computations and Provable Complexity Properties</i>,<br />
SIAM, 1978.<br />
<br />
<span id="har87" style="color:maroon">[Har87]</span><br />
J. Hartmanis.<br />
The collapsing hierarchies,<br />
<i>Bulletin of the EATCS</i> 33, October 1987.<br />
[http://external.nj.nec.com/homepages/fortnow/beatcs/column33.ps http://external.nj.nec.com/homepages/fortnow/beatcs/column33.ps].<br />
<br />
<span id="har87b" style="color:maroon">[Har87b]</span><br />
J. Hartmanis.<br />
Sparse complete sets for NP and the optimal collapse of the polynomial hierarchy,<br />
<i>Bulletin of the EATCS</i> 32, June 1987.<br />
[http://external.nj.nec.com/homepages/fortnow/beatcs/column32.ps http://external.nj.nec.com/homepages/fortnow/beatcs/column32.ps].<br />
<br />
<span id="has87" style="color:maroon">[Has87]</span><br />
J. H&aring;stad.<br />
<i>Computational Limitations for Small-Depth Circuits</i>,<br />
MIT Press, 1987.<br />
<br />
<span id="has88" style="color:maroon">[Has88]</span><br />
J. H&aring;stad.<br />
Oneway permutations in NC<sup>0</sup>,<br />
<i>Information Processing Letters</i> 26:153-155, 1988.<br />
<br />
<span id="has90" style="color:maroon">[Has90]</span><br />
J. H&aring;stad. Tensor rank is NP-complete, ''J. Algorithms'', 11(4):644-654, 1990.<br />
<br />
<span id="has01" style="color:maroon">[Has01]</span><br />
J. H&aring;stad.<br />
Some optimal inapproximability results,<br />
''Journal of the ACM'', 48(4):798-3859, 2001.<br />
[http://www-sunos4.nada.kth.se/~johanh/optimalinap.ps http://www-sunos4.nada.kth.se/~johanh/optimalinap.ps]<br />
<br />
<span id="hcc92" style="color:maroon">[HCC+92]</span><br />
J. Hartmanis, R. Chang, S. Chari, D. Ranjan, and P. Rohatgi.<br />
Relativization: a revisionistic retrospective,<br />
<i>Bulletin of the EATCS</i> 47, June 1992.<br />
[http://external.nj.nec.com/homepages/fortnow/beatcs/column47.ps http://external.nj.nec.com/homepages/fortnow/beatcs/column47.ps].<br />
<br />
<span id="hck88" style="color:maroon">[HCK+88]</span><br />
J. Hartmanis, R. Chang, J. Kadin, and S. G. Mitchell.<br />
Some observations about relativization of space bounded computations,<br />
<i>Bulletin of the EATCS</i> 35, June 1988.<br />
[http://external.nj.nec.com/homepages/fortnow/beatcs/column35.ps http://external.nj.nec.com/homepages/fortnow/beatcs/column35.ps].<br />
<br />
<span id="hel84" style="color:maroon">[Hel84a]</span><br />
H. Heller.<br />
Relativized polynomial hierarchies extending two levels,<br />
<i>Mathematical Systems Theory</i> 17(2):71-84, 1984.<br />
<br />
<span id="hel84b" style="color:maroon">[Hel84b]</span><br />
H. Heller.<br />
On Relativized Polynomial and Exponential Computations,<br />
<i>SIAM Journal on Computing</i> 13(4):717-725, 1984.<br />
<br />
<span id="hel86" style="color:maroon">[Hel86]</span><br />
H. Heller.<br />
On Relativized Exponential and Probabilistic Complexity Classes,<br />
Inform. and Control 71 (1986), no. 3, 231--243<br />
<br />
<span id="hem89" style="color:maroon">[Hem89]</span><br />
L. Hemachandra.<br />
The strong exponential hierarchy collapses,<br />
<i>Journal of Computer and System Sciences</i> 39(3):299-322, 1989.<br />
<br />
<span id="her90" style="color:maroon">[Her90]</span><br />
U. Hertrampf.<br />
Relations among MOD-classes,<br />
<i>Theoretical Computer Science</i> 74:325-328, 1990.<br />
<br />
<span id="her97" style="color:maroon">[Her97]</span><br />
U. Hertrampf.<br />
Acceptance by transformation monoids (with an application to local self-reductions),<br />
<i>Proceedings of IEEE Complexity'97</i>, pp. 213-224, 1997.<br />
<br />
<span id="hes01" style="color:maroon">[Hes01]</span><br />
W. Hesse.<br />
Division is in uniform TC<sup>0</sup>,<br />
<i>Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP)</i>, 2001.<br />
[http://www.cs.umass.edu/~whesse/div.ps http://www.cs.umass.edu/~whesse/div.ps]<br />
<br />
<span id="hh76" style="color:maroon">[HH76]</span><br />
J. Hartmanis and J. Hopcroft.<br />
Independence results in computer science,<br />
<i>ACM SIGACT News</i> 8(4):13-24, 1976.<br />
<br />
<span id="hh86" style="color:maroon">[HH86]</span><br />
J. Hartmanis and L. Hemachandra.<br />
Complexity classes without machines: on complete languages for UP,<br />
<i>Proceedings of ICALP'86</i>, Springer-Verlag Lecture Notes in Computer Science volume 226, pp. 123-135, 1986.<br />
<br />
<span id="hhh98" style="color:maroon">[HHH98]</span><br />
E. Hemaspaandra, L. Hemaspaandra, and H. Hempel.<br />
What's up with downward collapse: using the easy-hard technique to link Boolean and polynomial hierarchy collapses,<br />
<i>SIGACT News</i> 29(3):10-22, 1998.<br />
arXiv:[http://arxiv.org/abs/cs.CC/9910002 cs.CC/9910002].<br />
<br />
<span id="hhk05" style="color:maroon">[HHK+05]</span><br />
L. Hemaspaandra, C. Homan, S. Kosub, and K. Wagner.<br />
The complexity of computing the size of an interval,<br />
Technical Report TR-856, Department of Computer Science, University of<br />
Rochester, 2005. This is an expanded version of [[#hkw01|HKW01]]<br />
<br />
<span id="hhn95" style="color:maroon">[HHN+95]</span><br />
L. Hemaspaandra, A. Hoene, A. Naik, M. Ogihara, A. Selman, T. Thierauf, and J. Wang.<br />
Nondeterministically selective sets,<br />
<i>International Journal of Foundations of Computer Science (IJFCS)</i>, 6(4):403-416, 1995.<br />
<br />
<span id="hhr97" style="color:maroon">[HHR97]</span><br />
E. Hemaspaandra, L. Hemaspaandra, and J. Rothe.<br />
Exact analysis of Dodgson elections: Lewis Carroll's 1876 voting system is complete for parallel access to NP,<br />
<i>Proceedings of ICALP'97</i>, Springer-Verlag Lecture Notes in Computer Science, 1997.<br />
arXiv:[http://arxiv.org/abs/cs.CC/9907036 cs.CC/9907036].<br />
<br />
<span id="hht97" style="color:maroon">[HHT97]</span><br />
Y. Han, L. Hemaspaandra, and T. Thierauf.<br />
Threshold computation and cryptographic security,<br />
<i>SIAM Journal on Computing</i> 26(1):59-78, 1997.<br />
<br />
<span id="hi02" style="color:maroon">[HI02]</span><br />
W. Hesse and N. Immerman.<br />
Complete problems for dynamic complexity classes,<br />
<i>Proceedings of Logic in Computer Science (LICS)</i>, 2002.<br />
[http://www.cs.umass.edu/~immerman/pub/completeLICS.pdf http://www.cs.umass.edu/~immerman/pub/completeLICS.pdf]<br />
<br />
<span id="hjv93" style="color:maroon">[HJV93]</span><br />
L. Hemaspaandra, R. Jain, and N. K. Vereshchagin.<br />
Banishing robust Turing completeness,<br />
<i>International Journal of Foundations of Computer Science</i>, 3-4:245-265, 1993.<br />
<br />
<span id="hkw01" style="color:maroon">[HKW01]</span><br />
L. Hemaspaandra, S. Kosub, and K. Wagner.<br />
The complexity of computing the size of an interval,<br />
<i>Proceedings of ICALP'01</i>, Springer-Verlag Lecture Notes in Computer Science, 2001.<br />
<br />
<span id="hls65" style="color:maroon">[HLS65]</span><br />
J. Hartmanis, P. L. Lewis II, and R. E. Stearns.<br />
Hierarchies of memory-limited computations,<br />
<i>Proceedings of the 6th Annual IEEE Symposium on Switching Circuit Theory and Logic Design</i>, pp. 179-190, 1965.<br />
<br />
<span id="hm13" style="color:maroon">[HM13]</span><br />
Aram W. Harrow, Ashley Montanaro.<br />
Testing product states, quantum Merlin-Arthur games and tensor optimisation,<br />
<i>Journal of the ACM</i> vol. 60 no. 1, 2013<br />
<br />
<span id="hmp93" style="color:maroon">[HMP+93]</span><br />
A. Hajnal, W. Maass, P. Pudl&aacute;k, M. Szegedy, and G. Tur&aacute;n.<br />
Threshold circuits of bounded depth,<br />
<i>Journal of Computer and System Sciences</i> 46(2):129-154, 1993.<br />
<br />
<span id="hn06" style="color:maroon">[HN06]</span><br />
D. Harnik and M. Naor.<br />
On the compressibility of NP instances and cryptographic applications.<br />
<i>Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS)</i>, 719-728, 2006.<br />
[http://www.cs.technion.ac.il/~harnik/Compress.pdf http://www.cs.technion.ac.il/~harnik/Compress.pdf]<br />
<br />
<span id="hno96" style="color:maroon">[HNO+96]</span><br />
L. Hemaspaandra, A. Naik, M. Ogihara, and A. Selman.<br />
Computing solutions uniquely collapses the polynomial hierarchy,<br />
<i>SIAM Journal on Computing</i> 25(4):697-708, 1996.<br />
ECCC [http://eccc.uni-trier.de/eccc-reports/1996/TR96-027/ TR96-027].<br />
<br />
<span id="ho02" style="color:maroon">[HO02]</span><br />
L. Hemaspaandra and M. Ogihara.<br />
<i>The Complexity Theory Companion</i>,<br />
Springer-Verlag, 2002.<br />
See also [http://www.cs.rochester.edu/u/lane/=companion/ http://www.cs.rochester.edu/u/lane/=companion/].<br />
<br />
<span id="hpv77" style="color:maroon">[HPV77]</span><br />
J. Hopcroft, W. Paul, and L. Valiant.<br />
On time versus space,<br />
<i>Journal of the ACM</i> 24(2):332-337, 1977.<br />
<br />
<span id="hrv00" style="color:maroon">[HRV00]</span><br />
U. Hertrampf, S. Reith, and H. Vollmer.<br />
A note on closure properties of logspace MOD classes,<br />
<i>Information Processing Letters</i> 75(3):91-93, 2000.<br />
[http://www.thi.uni-hannover.de/forschung/publikationen/daten/he-re-vo99.ps.gz http://www.thi.uni-hannover.de/forschung/publikationen/daten/he-re-vo99.ps.gz]<br />
<br />
<span id="hs65" style="color:maroon">[HS65]</span><br />
J. Hartmanis and R. E. Stearns.<br />
On the computational complexity of algorithms,<br />
<i>Transactions of the AMS</i> 117:285-305, 1965.<br />
<br />
<span id="hs92" style="color:maroon">[HS92]</span><br />
S. Homer and A. L. Selman.<br />
Oracles for structural properties: the isomorphism problem and public-key cryptography,<br />
<i>Journal of Computer and System Sciences</i> 44(2):287-301, 1992.<br />
<br />
<span id="ht03" style="color:maroon">[HT03]</span><br />
Christopher M. Homan, Mayur Thakur<br />
One-way permutations and self-witnessing languages<br />
<i>Journal of Computer and System Sciences</i> 67 (2003), 608--622.<br />
[https://www.sciencedirect.com/science/article/pii/S0022000003000680].<br />
<br />
<span id="ht06" style="color:maroon">[HT06]</span><br />
Lauri Hella , José María Turull-Torres<br />
Computing queries with higher-order logics<br />
<i>Theorical. Comput. Sci.</i> 355 (2006), 197--214.<br />
[http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6V1G-4J614M7-6&_user=1516330&_coverDate=04%2F11%2F2006&_rdoc=1&_fmt=high&_orig=search&_sort=d&_docanchor=&view=c&_searchStrId=1404146870&_rerunOrigin=google&_acct=C000053443&_version=1&_urlVersion=0&_userid=1516330&md5=6d794cde4e4a89dfa74f13967cdacb08].<br />
<br />
<br />
<br />
<span id="hy84" style="color:maroon">[HY84]</span><br />
J. Hartmanis and Y. Yesha.<br />
Computation times of NP sets of different densities,<br />
<i>Theoretical Computer Science</i> 34:17-32, 1984.<br />
<br />
===== I =====<br />
<br />
<span id="iba72" style="color:maroon">[Iba72]</span><br />
O. Ibarra.<br />
A note concerning nondeterministic tape complexities,<br />
<i>Journal of the ACM</i> 4:608-612, 1972.<br />
<br />
<span id="ikw01" style="color:maroon">[IKW01]</span><br />
R. Impagliazzo, V. Kabanets, and A. Wigderson.<br />
In search of an easy witness: exponential time vs. probabilistic polynomial time,<br />
<i>Proceedings of IEEE Complexity'2001</i>, 2001.<br />
[http://www.cs.sfu.ca/~kabanets/papers/exp_journal.ps.gz http://www.cs.sfu.ca/~kabanets/papers/exp_journal.ps.gz]<br />
<br />
<span id="il90" style="color:maroon">[IL90]</span><br />
R. Impagliazzo and L. A. Levin.<br />
No better ways to generate hard NP instances than picking uniformly at random,<br />
<i>Proceedings of IEEE FOCS'90</i>, pp. 812-821, 1990.<br />
<br />
{{Reference<br />
|tag=IM03<br />
|title=A zero one law for RP<br />
|authors=R. Impagliazzo and P. Moser<br />
|journal=Proceedings of the 18th Conference on Computational Complexity<br />
|srcdetail=48-52. IEEE Computer Society Press, 2003<br />
}}<br />
<br />
{{Reference<br />
|tag=Imp95<br />
|title=A personal view of average-case complexity<br />
|authors=R. Impagliazzo<br />
|journal=Proceedings of the 10th Conference on Structure in Complexity Theory<br />
|srcdetail=134-147. IEEE Computer Society Press, 1995<br />
}}<br />
<br />
<span id="imm82" style="color:maroon">[Imm82]</span><br />
N. Immerman.<br />
Relational queries computable in in polynomial time.<br />
<i>14th ACM STOC Symp. (1987), 86-104</i><br />
<br />
<br />
<span id="imm83" style="color:maroon">[Imm83]</span><br />
N. Immerman.<br />
Languages That Capture Complexity Classes<br />
<i>15th ACM STOC Symp. (1983), 347-354</i><br />
[http://www.cs.umass.edu/~immerman/pub/capture.pdf]<br />
<br />
<span id="imm88" style="color:maroon">[Imm88]</span><br />
N. Immerman.<br />
Nondeterministic space is closed under complement,<br />
<i>SIAM Journal on Computing</i>, 17:935-938, 1988.<br />
<br />
<span id="imm89" style="color:maroon">[Imm89]</span><br />
N. Immerman.<br />
Expressibility and Parallel Complexity<br />
<i>SIAM Journal on Computing</i>, 18:625-638, 1989.<br />
[http://www.cs.umass.edu/~immerman/pub/parallel.pdf]<br />
<br />
<span id="imm98" style="color:maroon">[Imm98]</span><br />
N. Immerman.<br />
<i>Descriptive Complexity</i>,<br />
Springer Graduate Texts in Computer Science, 1998.<br />
<br />
<span id="imp02" style="color:maroon">[Imp02]</span><br />
R. Impagliazzo.<br />
Hardness as randomness: a survey of universal derandomization,<br />
<i>Proceedings of the ICM</i>, Beijing, vol. 3, pp. 649-658, 2002.<br />
arXiv:[http://arxiv.org/abs/cs.CC/0304040 cs.CC/0304040].<br />
<br />
<span id="in96" style="color:maroon">[IN96]</span><br />
R. Impagliazzo and M. Naor.<br />
Efficient cryptographic schemes provably as secure as subset sum,<br />
<i>Journal of Cryptology</i> 9(4):199-216, 1996.<br />
[http://www.wisdom.weizmann.ac.il/~naor/PAPERS/subset.ps.gz http://www.wisdom.weizmann.ac.il/~naor/PAPERS/subset.ps.gz]<br />
<br />
<span id="ipz01" style="color:maroon">[IPZ01]</span><br />
R. Impagliazzo, R. Paturi, and F. Zane.<br />
Which problems have strongly exponential complexity,<br />
<i>Journal of Computer and System Sciences</i> 63(4):512-530, 2001.<br />
[http://cm.bell-labs.com/cm/ms/who/francis/papers/focs98-subexp.pdf http://cm.bell-labs.com/cm/ms/who/francis/papers/focs98-subexp.pdf].<br />
<br />
<span id="is91" style="color:maroon">[IS91]</span><br />
R. Impagliazzo and M. Sudan.<br />
Private communication,<br />
cited in [#bg94" style="color:maroon">[BG94], 1991.<br />
<br />
<span id="it89" style="color:maroon">[IT89]</span><br />
R. Impagliazzo and G. Tardos.<br />
Decision versus search problems in super-polynomial time,<br />
in <i>Proceedings of IEEE FOCS 1989</i>, pp. 222-227, 1989.<br />
<br />
<span id="iv12" style="color:maroon">[IV12]</span><br />
T. Ito and T. Vidick.<br />
A multi-prover interactive proof for NEXP sound against entangled provers,<br />
to appear in <i>Proceedings of IEEE FOCS 2012</i><br />
arXiv:[http://arxiv.org/abs/1207.0550 1207.0550].<br />
<br />
<span id="iw97" style="color:maroon">[IW97]</span><br />
R. Impagliazzo and A. Wigderson.<br />
P=BPP if E requires exponential circuits: derandomizing the XOR lemma,<br />
<i>Proceedings of ACM STOC'97</i>, pp. 220-229, 1997.<br />
<br />
===== J =====<br />
<br />
<span id="jer07" style="color:maroon">[Jeř07]</span><br />
E. Jeřábek.<br />
Approximate counting in bounded arithmetic,<br />
''Journal of Symbolic Logic'' 72(3):959–993, 2007.<br />
<br />
<span id="jer12" style="color:maroon">[Jeř12]</span><br />
Emil Jeřábek.<br />
Integer factoring and modular square roots,<br />
http://arxiv.org/abs/1207.5220<br />
<br />
<span id="JJUW09" style="color:maroon">[JJUW09]</span><br />
Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, and John Watrous.<br />
QIP = PSPACE<br />
arXiv:[http://arxiv.org/abs/0907.4737 0907.4737], 2009.<br />
<br />
<span id="jks02" style="color:maroon">[JKS02]</span><br />
J. C. Jackson, A. R. Klivans, and R. A. Servedio.<br />
Learnability beyond AC<sup>0</sup>,<br />
<i>Proceedings of ACM STOC'2002</i>, pp. 776-784, 2002.<br />
<br />
<span id="jl95" style="color:maroon">[JL95]</span><br />
D. W. Juedes and J. H. Lutz.<br />
The complexity and distribution of hard problems,<br />
<i>SIAM Journal on Computing</i> 24(2):279-295, 1995.<br />
[http://www.cs.iastate.edu/~lutz/%3DPAPERS/cdhp.ps http://www.cs.iastate.edu/~lutz/%3DPAPERS/cdhp.ps]<br />
<br />
<span id="joh90" style="color:maroon">[Joh90]</span><br />
D. S. Johnson.<br />
A catalog of complexity classes,<br />
chapter 2 in <i>Handbook of Theoretical Computer Science</i>, Volume A (J. van Leeuwen, editor), Elsevier, 1990.<br />
<br />
<span id="jon98" style="color:maroon">[Jon98]</span><br />
Neil D. Jones<br />
Logspace and Ptime Characteried by Programming Languages<br />
[ftp://ftp.diku.dk/pub/diku/semantics/papers/D-398.ps.gz]<br />
<br />
<span id="jpy88" style="color:maroon">[JPY88]</span><br />
D. S. Johnson, C. H. Papadimitriou, and M. Yannakakis.<br />
How easy is local search?,<br />
<i>Journal of Computer and System Sciences</i> 37:79-100, 1988.<br />
<br />
<span id="jsv01" style="color:maroon">[JSV01]</span><br />
M. Jerrum, A. Sinclair, and E. Vigoda.<br />
A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries,<br />
<i>Proceedings of ACM STOC'2001</i>, pp. 712-721, 2001.<br />
ECCC [http://eccc.uni-trier.de/eccc-reports/2000/TR00-079/ TR00-079].<br />
<br />
<span id="jun85" style="color:maroon">[Jun85]</span><br />
H. Jung.<br />
On probabilistic time and space,<br />
<i>Proceedings of 12th International Colloquium on Automata, Languages, and Programming (ICALP)</i>, Lecture Notes in Computer Science, 194:310-317, 1985.<br />
<br />
<span id="jw04" style="color:maroon">[JW04]</span><br />
M. Jerrum and U. Wagner.<br />
<i>Counting, Sampling, and Integrating: Algorithms and Complexity</i>,<br />
Chapter 3 (lecture notes labeled as under construction).<br />
[http://www.dcs.ed.ac.uk/home/mrj/ETHbook/chap3.ps http://www.dcs.ed.ac.uk/home/mrj/ETHbook/chap3.ps].<br />
<br />
<span id="jw09" style="color:maroon">[JW09]</span><br />
Rahul Jain and John Watrous.<br />
Parallel approximation of non-interactive zero-sum quantum games.<br />
<i>Proceedings of the 24th Annual IEEE Conference on Computational Complexity</i>, pages 243–253, 2009.<br />
arXiv:[http://arxiv.org/abs/0808.2775 0808.2775 [quant-ph]].<br />
<br />
<span id="jwb03" style="color:maroon">[JWB03]</span><br />
D. Janzing, P. Wocjan, and T. Beth.<br />
Cooling and low energy state preparation for 3-local Hamiltonians are FQMA-complete,<br />
arXiv:[http://arxiv.org/abs/quant-ph/0303186 quant-ph/0303186], 2003.<br />
<br />
<span id="jy88" style="color:maroon">[JY88]</span><br />
D. S. Johnson and M. Yannakakis.<br />
On generating all maximal independent sets,<br />
<i>Information Processing Letters</i> 27(3):119-123, 1988.<br />
<br />
===== K =====<br />
<br />
<span id="kad88" style="color:maroon">[Kad88]</span><br />
J. Kadin.<br />
The polynomial time hierarchy collapses if the Boolean hierarchy collapses,<br />
<i>SIAM Journal on Computing</i> 17:1263-1282, 1988.<br />
<br />
<span id="kan82" style="color:maroon">[Kan82]</span><br />
R. Kannan.<br />
Circuit-size lower bounds and non-reducibility to sparse sets,<br />
<i>Information and Control</i> 55:40-56, 1982.<br />
<br />
<span id="kar72" style="color:maroon">[Kar72]</span><br />
R. M. Karp.<br />
Reducibility among combinatorial problems,<br />
<i>Complexity of Computer Computations</i> (J. W. Thatcher and R. E. Miller, eds.), Plenum Press, 1972.<br />
<br />
<span id="kar86" style="color:maroon">[Kar86]</span><br />
H. Karloff.<br />
A Las Vegas algorithm for maximum matching,<br />
<i>Combinatorica</i> 6:387-392, 1986.<br />
<br />
<span id="kf84" style="color:maroon">[KF84]</span><br />
C. M. R. Kintala and P. Fischer.<br />
Refining nondeterminism in relativized complexity classes,<br />
<i>SIAM Journal on Computing</i> 13:329-337, 1984.<br />
<br />
<span id="kha79" style="color:maroon">[Kha79]</span><br />
L. G. Khachiyan.<br />
A polynomial algorithm for linear programming,<br />
<i>Soviet Math Doklady</i> 20:191-194, 1979.<br />
<br />
<span id="kha93" style="color:maroon">[Kha93]</span><br />
M. Kharitonov.<br />
Cryptographic hardness of distribution-specific learning,<br />
<i>Proceedings of ACM STOC'93</i>, pp. 372-381, 1993.<br />
<br />
<span id="ki02" style="color:maroon">[KI02]</span><br />
V. Kabanets and R. Impagliazzo.<br />
Derandomizing polynomial identity tests means proving circuit lower bounds,<br />
ECCC [http://eccc.uni-trier.de/eccc-reports/2002/TR02-055/ TR02-055], 2002.<br />
<br />
<span id="kkr04" style="color:maroon">[KKR04]</span><br />
J. Kempe, A. Kitaev, and O. Regev.<br />
The Complexity of the Local Hamiltonian Problem,<br />
<i>SIAM Journal of Computing</i>, Vol. 35(5), p. 1070-1097 (2006).<br />
arXiv:[http://arxiv.org/abs/quant-ph/0406180 quant-ph/0406180].<br />
<br />
<span id="kl82" style="color:maroon">[KL82]</span><br />
R. M. Karp and R. J. Lipton.<br />
Turing machines that take advice,<br />
<i>Enseign. Math.</i> 28:191-201, 1982.<br />
<br />
<span id="kle71" style="color:maroon">[Kle71]</span><br />
S. C. Kleene.<br />
<i>Introduction to Metamathematics</i>,<br />
Elsevier, 1971.<br />
<br />
<span id="km02" style="color:maroon">[KM02]</span><br />
H. Kobayashi and K. Matsumoto.<br />
Quantum multi-prover interactive proof systems with limited prior entanglement,<br />
<i>Proceedings of ISAAC'2002</i>, pp. 115-127, 2002.<br />
arXiv:[http://arxiv.org/abs/cs.CC/0102013 cs.CC/0102013].<br />
<br />
<span id="km92" style="color:maroon">[KM92]</span><br />
D. Koller and N. Megiddo.<br />
On the Complexity of Two-person Zero-sum Games in Extensive Form,<br />
Games and Economic Behavior 4, 528-552, 1992.<br />
[http://theory.stanford.edu/~megiddo/pdf/recall.pdf http://theory.stanford.edu/~megiddo/pdf/recall.pdf]<br />
<br />
<span id="km99" style="color:maroon">[KM99]</span><br />
A. Klivans and D. van Melkebeek.<br />
Graph nonisomorphism has subexponential size proofs unless the polynomial hierarchy collapses,<br />
in <i>Proceedings of ACM STOC'99</i>, pp. 659-667, 1999.<br />
<br />
<span id="kms99" style="color:maroon">[KMS+99]</span><br />
S. Khanna, R. Motwani, M. Sudan, and U. Vazirani.<br />
On syntactic versus computational views of approximability,<br />
<i>SIAM Journal on Computing</i> 28:164-191, 1999.<br />
ECCC [http://eccc.uni-trier.de/eccc-reports/1995/TR95-023/ TR95-023].<br />
<br />
<span id="kmy01" style="color:maroon">[KMY01]</span><br />
H. Kobayashi, K. Matsumoto, and T. Yamakami.<br />
Quantum certificate verification: single versus multiple quantum certificates,<br />
arXiv:[http://arxiv.org/abs/quant-ph/0110006 quant-ph/0110006], 2001.<br />
<br />
<span id="ko82" style="color:maroon">[Ko82]</span><br />
K. Ko.<br />
Some observations on the probabilistic algorithms and NP-hard problems,<br />
<i>Information Processing Letters</i> 14(1):39-43, 1982.<br />
<br />
<span id="ko85" style="color:maroon">[Ko85]</span><br />
K. Ko.<br />
On some natural complete operators,<br />
<i>Theoretical Computer Science</i> 37(1):1-30, 1985.<br />
<br />
<span id="kob02" style="color:maroon">[Kob02]</span><br />
H. Kobayashi.<br />
Non-interactive quantum statistical and perfect zero-knowledge,<br />
arXiv:[http://arxiv.org/abs/quant-ph/0207158 quant-ph/0207158], 2002.<br />
<br />
<span id="kob89" style="color:maroon">[Kob89]</span><br />
J. K&ouml;bler.<br />
<i>Strukturelle Komplexit&auml;t von Anzahlproblemen</i>,<br />
PhD thesis, Universit&auml;t Stuttgart, 1989.<br />
<br />
<span id="koi96" style="color:maroon">[Koi96]</span><br />
P. Koiran.<br />
Hilbert's Nullstellensatz is in the polynomial hierarchy,<br />
<i>Journal of Complexity</i> 12(4):273-286, 1996,<br />
DIMACS [http://dimacs.rutgers.edu/TechnicalReports/abstracts/1996/96-27.html TR 96-27].<br />
<br />
<span id="koz92" style="color:maroon">[Koz92]</span><br />
D. C. Kozen.<br />
On the Myhill-Nerode theorem for trees,<br />
<i>Bulletin of the EATCS</i> 47:170-173, 1992.<br />
<br />
<span id="koz97" style="color:maroon">[Koz97]</span><br />
D. C. Kozen.<br />
<i>Automata and Computability</i>,<br />
Springer-Verlag, 1997.<br />
<br />
<span id="kp89" style="color:maroon">[KP89]</span><br />
Jan Krajicek and Pavel Pudlak.<br />
Propositional Proof Systems, the Consistency of First Order Theories and the Complexity of Computations,<br />
<i>J. Symb. Log.</i>, 54:1063-79, 1989.<br />
<br />
<span id="kr03" style="color:maroon">[KR03]</span><br />
J. Kempe and O. Regev.<br />
3-Local Hamiltonian is QMA-complete,<br />
<i>Quantum Inf. Comput.</i>, 3(3):258-264, 2003.<br />
arXiv:[http://arxiv.org/abs/quant-ph/0302079 quant-ph/0302079].<br />
<br />
<span id="kra.." style="color:maroon">[Kra..]</span><br />
H. Krawczyk.<br />
Unpublished.<br />
<br />
<span id="krc00" style="color:maroon">[KRC00]</span><br />
V. Kabanets, C. Rackoff, and S. A. Cook.<br />
Efficiently approximable real-valued functions,<br />
ECCC [http://eccc.uni-trier.de/eccc-reports/2000/TR00-034/ TR00-034], 2000.<br />
<br />
<span id="kre88" style="color:maroon">[Kre88]</span><br />
M. Krentel.<br />
The complexity of optimization problems,<br />
<i>Journal of Computer and System Sciences</i> 36:490-509, 1988.<br />
<br />
<span id="krs90" style="color:maroon">[KRS90]</span><br />
C. P. Kruskal, L. Rudolph, and M. Snir.<br />
A complexity theory of efficient parallel algorithms,<br />
<i>Theoretical Computer Science</i> 71:95-132, 1990.<br />
<br />
{{Reference<br />
|tag=KS05<br />
|authors=N. Kayal and N. Saxena<br />
|title=On the ring isomorphism and automorphism problems<br />
|journal=Proceedings of the 20th Annual IEEE Conference on Computational Complexity<br />
|srcdetail=2-12, 2005}}<br />
<br />
<span id="kst89" style="color:maroon">[KST+89]</span><br />
J. K&ouml;bler, U. Sch&ouml;ning, and J. Tor&aacute;n.<br />
On counting and approximation,<br />
<i>Acta Informatica</i> 26:363-379, 1989.<br />
<br />
<span id="kst89b" style="color:maroon">[KST+89b]</span><br />
J. K&ouml;bler, U. Sch&ouml;ning, S. Toda, and J. Tor&aacute;n.<br />
Turing machines with few accepting computations and low sets for PP,<br />
<i>Proceedings of IEEE Complexity'89</i>, pp. 208-215, 1989.<br />
[http://www.informatik.hu-berlin.de/Forschung_Lehre/algorithmenII/Papers/few.ps.gz http://www.informatik.hu-berlin.de/Forschung_Lehre/algorithmenII/Papers/few.ps.gz]<br />
<br />
<span id="kst92" style="color:maroon">[KST92]</span><br />
J. K&ouml;bler, U. Sch&ouml;ning, and J. Tor&aacute;n.<br />
Graph isomorphism is low for PP,<br />
<i>Computational Complexity</i> 2:301-330, 1992.<br />
<br />
<span id="kst93" style="color:maroon">[KST93]</span><br />
J. K&ouml;bler, U. Sch&ouml;ning, and J. Tor&aacute;n.<br />
<i>The Graph Isomorphism Problem: Its Structural Complexity</i>,<br />
Birkh&auml;user, 1993.<br />
<br />
<span id="ksv02" style="color:maroon">[KSV02]</span><br />
A. Kitaev, A. Shen, and M. N. Vyalyi.<br />
<i>Classical and Quantum Computation</i>,<br />
American Mathematical Society, 2002.<br />
<br />
<span id="kt94" style="color:maroon">[KT94]</span><br />
P. G. Koliatis and M. N. Thakur.<br />
Logical definability of NP optimization problems,<br />
<i>Information and Computation</i> 115:321-353, 1994.<br />
<br />
<span id="kt96" style="color:maroon">[KT96]</span><br />
J. K&ouml;bler and S. Toda.<br />
On the power of generalized MOD-classes,<br />
<i>Mathematical Systems Theory</i> 29(1):33-46, 1996.<br />
[ftp://theorie.informatik.uni-ulm.de/pub/papers/ti/mod.ps.gz ftp://theorie.informatik.uni-ulm.de/pub/papers/ti/mod.ps.gz]<br />
<br />
<span id="kup09" style="color:maroon">[Kup09]</span><br />
G. Kuperberg.<br />
How hard is it to approximate the Jones polynomial?, 2009.<br />
arXiv:[http://arxiv.org/abs/0908.0512 quant-ph/0908.0512v1].<br />
<br />
<span id="kur64" style="color:maroon">[Kur64]</span><br />
S. Y. Kuroda.<br />
Classes of languages and linear-bounded automata,<br />
<i>Information and Control</i> 7:207-233, 1964.<br />
<br />
<span id="kur83" style="color:maroon">[Kur83]</span><br />
S. Kurtz.<br />
On the random oracle hypothesis,<br />
<i>Information and Control</i> 57:40-47, 1983.<br />
<br />
<span id="kur85" style="color:maroon">[Kur85]</span><br />
S. Kurtz.<br />
On Relativized Exponential and Probabilistic Complexity Classes,<br />
<i>Information and Control</i> 71:231-243, 1985.<br />
<br />
<span id="kuw86" style="color:maroon">[KUW86]</span><br />
R. Karp, E. Upfal, and A. Wigderson.<br />
Constructing a perfect matching is in random NC,<br />
<i>Combinatorica</i> 6:35-48, 1986.<br />
<br />
<span id="kv88" style="color:maroon">[KV88]</span><br />
M. Karpinski and R. Verbeek.<br />
Randomness, provability, and the separation of Monte Carlo time and space,<br />
<i>Lecture Notes in Computer Science</i> 270, pp. 189-207, Springer, 1988.<br />
<br />
<span id="kv94" style="color:maroon">[KV94]</span><br />
M. Kearns and L. Valiant.<br />
Cryptographic limitations on learning Boolean formulae and finite automata,<br />
<i>Journal of the ACM</i> 41(1):67-95, 1994.<br />
[http://www.cis.upenn.edu/~mkearns/papers/crypto.pdf http://www.cis.upenn.edu/~mkearns/papers/crypto.pdf]<br />
<br />
<span id="kv96" style="color:maroon">[KV96]</span><br />
M. Karpinski and R. Verbeek.<br />
On Randomized Versus Deterministic Computation,<br />
Theoret. Comput. Sci. 154 (1996), no. 1, 23--39.<br />
ECCC [http://eccc.uni-trier.de/eccc-reports/1995/TR95-021/ TR95-021].<br />
<br />
<span id="kw.." style="color:maroon">[KW..]</span><br />
A. Kitaev and J. Watrous.<br />
Unpublished.<br />
<br />
<span id="kw00" style="color:maroon">[KW00]</span><br />
A. Kitaev and J. Watrous.<br />
Parallelization, amplification, and exponential time simulation of quantum interactive proof systems,<br />
<i>Proceedings of ACM STOC'2000</i>, pp. 608-617, 2000.<br />
[https://cs.uwaterloo.ca/~watrous/Papers/QuantumInteractiveProofs.pdf https://cs.uwaterloo.ca/~watrous/Papers/QuantumInteractiveProofs.pdf]<br />
<br />
<span id="kw88" style="color:maroon">[KW88]</span><br />
M. Karchmer and A. Wigderson.<br />
Monotone circuits for connectivity require superlogarithmic depth,<br />
<i>Proceedings of ACM STOC'88</i>, pp. 539-550, 1988.<br />
<br />
<span id="kw93" style="color:maroon">[KW93]</span><br />
M. Karchmer and A. Wigderson.<br />
On span programs,<br />
<i>Proceedings of IEEE Complexity'93</i>, pp. 102-111, 1993.<br />
<br />
<span id="kw98" style="color:maroon">[KW98]</span><br />
J. K&ouml;bler and O. Watanabe.<br />
New collapse consequences of NP having small circuits,<br />
<i>SIAM Journal on Computing</i> 28(1):311-324, 1998.<br />
[http://www.informatik.hu-berlin.de/forschung/gebiete/algorithmenII/Publikationen/Papers/collapse.ps.gz http://www.informatik.hu-berlin.de/forschung/gebiete/algorithmenII/Publikationen/Papers/collapse.ps.gz]<br />
<br />
===== L =====<br />
<br />
<span id="lad75" style="color:maroon">[Lad75]</span><br />
R. Ladner.<br />
On the structure of polynomial time reducibility,<br />
<i>Journal of the ACM</i> 22:155-171, 1975.<br />
<br />
<span id="lau83" style="color:maroon">[Lau83]</span><br />
C. Lautemann.<br />
BPP and the polynomial time hierarchy,<br />
<i>Information Processing Letters</i> 17:215-218, 1983.<br />
<br />
<span id="lee02" style="color:maroon">[Lee02]</span><br />
T. Lee.<br />
Arithmetical definability over finite structures,<br />
Mathematical Logic Quarterly, Vol. 49(4), 2003. <br />
[http://www.lri.fr/~lee/arith.pdf http://www.lri.fr/~lee/arith.pdf].<br />
<br />
<span id="lev73" style="color:maroon">[Lev73]</span><br />
L. A. Levin.<br />
Universal search problems (in Russian),<br />
<i>Problemy Peredachi Informatsii</i> 9(3):265-266, 1973.<br />
<br />
<span id="lev86" style="color:maroon">[Lev86]</span><br />
L. A. Levin.<br />
Average case complete problems,<br />
<i>SIAM Journal on Computing</i>, 15:285-286, 1986.<br />
<br />
<span id="lfk90" style="color:maroon">[LFK+90]</span><br />
C. Lund, L. Fortnow, H. Karloff, and N. Nisan.<br />
Algebraic methods for interactive proofs,<br />
<i>Proceedings of IEEE FOCS'90</i>, pp. 1-10, 1990.<br />
[http://people.cs.uchicago.edu/~fortnow/papers/ip.ps http://people.cs.uchicago.edu/~fortnow/papers/ip.ps]<br />
<br />
<span id="li93" style="color:maroon">[Li93]</span><br />
L. Li.<br />
<i>On the Counting Functions</i>,<br />
PhD thesis, University of Chicago, 1993.<br />
<br />
{{Reference<br />
|tag=LiRe93<br />
|authors=M. Liskiewicz, R. Reischuk<br />
|title=The complexity world below logarithmic space<br />
|journal=Proceedings of the Structure in Complexity Theory Conference<br />
|srcdetail=1993, 64-78<br />
}}<br />
<br />
<span id="li11" style="color:maroon">[Li11]</span><br />
Y. D. Li.<br />
BQP and PPAD,<br />
<i>Electronic Colloquium on Computational Complexity</i> TR11-103, 2011.<br />
<br />
<span id="ll76" style="color:maroon">[LL76]</span><br />
R. Ladner and N. A. Lynch.<br />
Relativization of questions about log space computability,<br />
<i>Mathematical Systems Theory</i> 10:19-32, 1976.<br />
<br />
<span id="lmn93" style="color:maroon">[LMN93]</span><br />
N. Linial, Y. Mansour, and N. Nisan.<br />
Constant depth circuits, Fourier transform, and learnability,<br />
<i>Journal of the ACM</i> 40(3):607-620, 1993.<br />
<br />
<span id="lmt97" style="color:maroon">[LMT97]</span><br />
K. Lange, P. McKenzie, and A. Tapp.<br />
Reversible space equals deterministic space (extended abstract),<br />
<i>Proceedings of IEEE FOCS'97</i>, pp. 45-50, 1997.<br />
<br />
<span id="lp82" style="color:maroon">[LP82]</span><br />
H. R. Lewis and C. H. Papadimitriou.<br />
Symmetric space-bounded computation,<br />
<i>Theoretical Computer Science</i> 19:161-187, 1982.<br />
<br />
<span id="ls74" style="color:maroon">[LS74]</span><br />
E. A. Lamagna and J. E. Savage<br />
Combinational complexity of some monotone functions,<br />
<i>FOCS</i> 140-44, 1974.<br />
<br />
<span id="lut91" style="color:maroon">[Lut91]</span><br />
J. H. Lutz.<br />
An upward measure separation theorem,<br />
<i>Theoretical Computer Science</i> 81:127-135, 1991.<br />
<br />
{{Reference<br />
|tag=Lut93<br />
|authors=J. H. Lutz<br />
|title=The quantitative structure of exponential time<br />
|journal=Proc. 8th Structure in Complexity Theory Conference<br />
|srcdetail=(IEEE Comput. Soc. Press, 1993) 158-175<br />
}}[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.53.1845&rep=rep1&type=pdf]<br />
<br />
<span id="lv97" style="color:maroon">[LV97]</span><br />
M. Li and P. Vit&aacute;nyi.<br />
<i>An Introduction to Kolmogorov Complexity and Its Applications</i> (second edition),<br />
Springer, 1997.<br />
<br />
===== M =====<br />
<br />
<span id="m08" style="color:maroon">[M08]</span><br />
L. Malka.<br />
How to achieve perfect simulation, and a complete problem for non-interactive perfect zero-knowledge. <i>IACR 5th Theory of Cryptography Conference (TCC)</i>, 2008.<br />
[http://www.cs.uvic.ca/~liorma/publications/NIZK9.pdf].<br />
<br />
<span id="mah82" style="color:maroon">[Mah82]</span><br />
S. R. Mahaney.<br />
Sparse complete sets for NP: Solution of a conjecture by Berman and Hartmanis,<br />
<i>Journal of Computer and System Sciences</i> 25:130-143, 1982.<br />
<br />
<span id="may94" style="color:maroon">[May94]</span><br />
E. Mayordomo.<br />
Almost every set in exponential time is P-bi-immune,<br />
<i>Theoretical Computer Science</i> 136(2):487-506, 1994.<br />
<br />
<span id="may94b" style="color:maroon">[May94b]</span><br />
E. Mayordomo.<br />
<i>Contributions to the study of resource-bounded measure</i>,<br />
PhD thesis, Universitat Politecnica de Catalunya, 1994.<br />
<br />
<span id="ms89" style="color:maroon">[MS89]</span><br />
E.W. Mayr and A. Subramanian. <br />
The complexity of circuit value and network stability, Proceedings of the Fourth Annual Conference on <i>Structure in Complexity Theory</i>, pp.114-123, 1989.<br />
<br />
<span id="mc00" style="color:maroon">[MC00]</span><br />
C. Moore and J. P. Crutchfield.<br />
Quantum automata and quantum grammars,<br />
<i>Theoretical Computer Science</i> 237:275-306, 2000.<br />
<br />
{{Reference<br />
|tag=Mel00<br />
|authors=D. Melkebeek<br />
|title=The zero-one law holds for BPP<br />
|journal=Theoretical Computer Science<br />
|srcdetail=Volume 244, Issues 1-2, 6 August 2000, Pages 283-288<br />
}}<br />
<br />
<span id="mes99" style="color:maroon">[Mes99]</span><br />
J. Messner.<br />
On optimal algorithms and optimal proof systems,<br />
<i>Lecture Notes in Computer Science</i> 1563:541-550, 1999.<br />
<br />
<span id="mil76" style="color:maroon">[Mil76]</span><br />
G. Miller.<br />
Riemann's hypothesis and tests for primality,<br />
<i>Journal of Computer and System Sciences</i>, 13:300-317, 1976.<br />
<br />
<span id="mil92" style="color:maroon">[Mil92]</span><br />
P. B. Miltersen.<br />
Circuit depth relative to a random oracle,<br />
<i>Information Processing Letters</i> 42(6):295-298, 1992.<br />
<br />
<span id="mn02" style="color:maroon">[MN02]</span><br />
C. Moore and M. Nilsson.<br />
Parallel quantum computation and quantum codes,<br />
<i>SIAM Journal on Computing</i> 31(3):799-815, 2002.<br />
arXiv:[http://arxiv.org/abs/quant-ph/9808027 quant-ph/9808027].<br />
<br />
<span id="mon80" style="color:maroon">[Mon80]</span><br />
B. Monien.<br />
On a subclass of pseudopolynomial problems,<br />
<i>Mathematical Foundations of Computer Science (MFCS'80)</i>, Springer LNCS 88, pp. 414-425, 1980.<br />
<br />
<span id="moo99" style="color:maroon">[Moo99]</span><br />
C. Moore.<br />
Quantum circuits: fanout, parity, and counting,<br />
ECCC [http://eccc.uni-trier.de/eccc-reports/1999/TR99-032/ TR99-032].<br />
<br />
<span id="mor01" style="color:maroon">[Mor01]</span><br />
T. Morioka.<br />
Classification of search problems and their definability in bounded arithmetic,<br />
master's thesis, University of Toronto, 2001.<br />
ECCC [http://eccc.uni-trier.de/eccc-reports/2001/TR01-082/ TR01-082].<br />
<br />
<span id="mp75" style="color:maroon">[MP75]</span><br />
D. E. Muller and F. P. Preparata.<br />
Bounds to complexities of networks for sorting and for switching,<br />
<i>Journal of the ACM</i> 22:195-201, 1975.<br />
<br />
<span id="mp91" style="color:maroon">[MP91]</span><br />
N. Megiddo and C. H. Papadimitriou.<br />
On total functions, existence theorems, and computational complexity,<br />
<i>Theoretical Computer Science</i> 81(2):317-324, 1991.<br />
<br />
<span id="mr95" style="color:maroon">[MR95]</span><br />
R. Motwani and P. Raghavan.<br />
<i>Randomized Algorithms</i>,<br />
Cambridge University Press, 1995.<br />
<br />
<span id="ms02" style="color:maroon">[MS02]</span><br />
K. Mulmuley and M. Sohoni.<br />
Geometric complexity theory I: An approach to the P vs. NP and related problems,<br />
<i>SIAM Journal on Computing</i> 31(2):496-526, 2002.<br />
<br />
<span id="muc56" style="color:maroon">[Muc56]</span><br />
A. A. Muchnik.<br />
On the unsolvability of the problem of reducibility in the theory of algorithms,<br />
<i>Doklady Akademii Nauk SSSR</i> 108:194-197, 1956.<br />
<br />
<span id="mv99" style="color:maroon">[MV99]</span><br />
P. B. Miltersen and N. V. Vinodchandran.<br />
Derandomizing Arthur-Merlin games using hitting sets,<br />
<i>Proceedings of IEEE FOCS'99</i>, pp. 71-80, 1999.<br />
<br />
<span id="mvv87" style="color:maroon">[MVV87]</span><br />
K. Mulmuley, U. V. Vazirani, and V. V. Vazirani.<br />
Matching is as easy as matrix inversion,<br />
<i>Proceedings of ACM STOC'87</i>, pp. 345-354, 1987.<br />
<br />
<span id="mvw99" style="color:maroon">[MVW99]</span><br />
P. B. Miltersen, N. V. Vinodchandran, and O. Watanabe.<br />
Super-polynomial versus half-exponential circuit size in the exponential hierarchy,<br />
<i>Proceedings of the 5th Annual Conference on Computing and Combinatorics (COCOON'99)</i>, pp. 210-220, Lecture Notes in Computer Science 1627, Springer-Verlag, 1999.<br />
<br />
<span id="mw05" style="color:maroon">[MW05]</span><br />
C. Marriott and J. Watrous.<br />
Quantum Arthur-Merlin Games,<br />
<i>Computational Complexity</i>, 14(2):122-152, 2005.<br />
arXiv:[http://arxiv.org/abs/cs/0506068 cs/0506068].<br />
<br />
===== N =====<br />
<br />
<span id="nc00" style="color:maroon">[NC00]</span><br />
M. Nielsen and I. Chuang.<br />
<i>Quantum Computation and Quantum Information</i>,<br />
Cambridge University Press, 2000.<br />
<br />
<span id="nhk00" style="color:maroon">[NHK00]</span><br />
M. Nakanishi, K. Hamaguchi, and T. Kashiwabara.<br />
Ordered quantum branching programs are more powerful than ordered probabilistic branching programs under a bounded-width restriction,<br />
<i>Proceedings of COCOON'2000 (Computing and Combinatorics)</i>, Springer LNCS 1858, pp. 467-476, 2000.<br />
<br />
<span id="nie02" style="color:maroon">[Nie02]</span><br />
G. Niemann and J. R. Woinowski.<br />
The Growing Context-Sensitive Languages Are the Acyclic Context-Sensitive Languages,<br />
<i>Developments in Language Theory</i>. LNCS 2295, pp. 197-205.<br />
</span><br />
<br />
<span id="nis02" style="color:maroon">[Nis02]</span><br />
T. Nishino.<br />
Mathematical models of quantum computation,<br />
New Gen. Comput. 20 (2002), no 4, 317-337.<br />
<br />
<span id="nis92" style="color:maroon">[Nis92]</span><br />
N. Nisan.<br />
RL is contained in SC,<br />
<i>Proceedings of ACM STOC'92</i>, pp. 619-623, 1992.<br />
<br />
<span id="nr97" style="color:maroon">[NR97]</span><br />
M. Naor and O. Reingold.<br />
Number-theoretic constructions of efficient pseudorandom functions,<br />
<i>Proceedings of IEEE FOCS'97</i>, pp. 458-467, 1997.<br />
<br />
<span id="nr98" style="color:maroon">[NR98]</span><br />
R. Niedermeier and P. Rossmanith.<br />
Unambiguous computations and locally definable acceptance types,<br />
<i>Theoretical Computer Science</i> 194:137-161, 1998.<br />
<br />
<span id="nrr01" style="color:maroon">[NRR01]</span><br />
M. Naor, O. Reingold, and A. Rosen.<br />
Pseudo-random functions and factoring,<br />
ECCC [http://eccc.uni-trier.de/eccc-reports/2001/TR01-064/ TR01-064].<br />
<br />
<span id="ns05" style="color:maroon">[NS05]</span><br />
A. Nickelsen and B. Schelm.<br />
Average-case computations - comparing AvgP, HP, and Nearly-P,<br />
<i>Proceedings of IEEE Complexity'2005</i>, pp. 235-242, 2005.<br />
[http://www.thi.uni-hannover.de/forschung/publikationen/daten/ni-sc05.pdf http://www.thi.uni-hannover.de/forschung/publikationen/daten/ni-sc05.pdf].<br />
<br />
<span id="nsw92" style="color:maroon">[NSW92]</span><br />
N. Nisan, E. Szemer&eacute;di, and A. Wigderson.<br />
Undirected connectivity in O(log<sup>1.5</sup>n) space,<br />
<i>Proceedings of IEEE FOCS'92</i>, pp. 24-29, 1992.<br />
<br />
<span id="nt95" style="color:maroon">[NT95]</span><br />
N. Nisan and A. Ta-Shma.<br />
Symmetric logspace is closed under complement,<br />
<i>Proceedings of ACM STOC'95</i>, pp. 140-146, 1995.<br />
ECCC [http://eccc.uni-trier.de/eccc-reports/1994/TR94-003/ TR94-003].<br />
<br />
<span id="nw94" style="color:maroon">[NW94]</span><br />
N. Nisan and A. Wigderson.<br />
Hardness versus randomness,<br />
<i>Journal of Computer and System Sciences</i> 49:149-167, 1994.<br />
<br />
<span id="ny03" style="color:maroon">[NY03]</span><br />
H. Nishimura and T. Yamakami.<br />
Polynomial time quantum computation with advice,<br />
arXiv:[http://arxiv.org/abs/quant-ph/0305100 quant-ph/0305100],<br />
ECCC [http://eccc.uni-trier.de/eccc-reports/2003/TR03-059/ TR03-059], 2003.<br />
<br />
<span id="ny03b" style="color:maroon">[NY03b]</span><br />
H. Nishimura and T. Yamakami.<br />
An algorithmic argument [http://www.cheatcodesforsim3.com/ for] query complexity lower bounds of advised quantum computation,<br />
arXiv:[http://arxiv.org/abs/quant-ph/0312003 quant-ph/0312003], 2003.<br />
<br />
===== O =====<br />
<br />
<span id="ogi94" style="color:maroon">[Ogi94]</span><br />
M. Ogihara.<br />
On serializable languages,<br />
<i>International Journal of Foundations of Computer Science</i> 5(3-4):303-318, 1994.<br />
<br />
<span id="oh93" style="color:maroon">[OH93]</span><br />
M. Ogihara and L. Hemachandra.<br />
A complexity theory for feasible closure properties,<br />
<i>Journal of Computer and System Sciences</i> 46(3):295-325, 1993.<br />
<br />
<span id="oka96" style="color:maroon">[Oka96]</span><br />
T. Okamoto.<br />
On relationships between statistical zero-knowledge proofs,<br />
<i>Proceedings of ACM STOC'96</i>, 1996.<br />
<br />
<span id="oks94" style="color:maroon">[OKS+94]</span><br />
P. Orponen, K.-I. Ko, U. Sch&ouml;ning, and O. Watanabe.<br />
Instance complexity,<br />
<i>Journal of the ACM</i> 41:96-121, 1994.<br />
<br />
<span id="ost91" style="color:maroon">[Ost91]</span><br />
R. Ostrovsky.<br />
One-way functions, hard on average problems and statistical zero-knowledge proofs,<br />
<i>Proceedings of IEEE Complexity'91</i>, pp. 51-59, 1991.<br />
<br />
<span id="ow93" style="color:maroon">[OW93]</span><br />
R. Ostrovsky and A. Wigderson.<br />
One-way functions are essential for non-trivial zero-knowledge,<br />
<i>Proceedings of the 2nd Israel Symposium on Theory of Computing and Systems (ISTCS-93)</i>, 1993.<br />
<br />
===== P =====<br />
<br />
<span id="pap83" style="color:maroon">[Pap83]</span><br />
C. H. Papadimitriou.<br />
Games against nature,<br />
<i>Proceedings of IEEE FOCS'83</i>, pp. 446-450, 1983.<br />
<br />
<span id="pap90" style="color:maroon">[Pap90]</span><br />
C. H. Papadimitriou.<br />
On graph-theoretic lemmata and complexity classes,<br />
<i>Proceedings of IEEE FOCS'90</i>, pp. 794-801, 1990.<br />
<br />
<span id="pap94" style="color:maroon">[Pap94]</span><br />
C. H. Papadimitriou.<br />
<i>Computational Complexity</i>,<br />
Addison-Wesley, 1994.<br />
<br />
<span id="pap94b" style="color:maroon">[Pap94b]</span><br />
C. H. Papadimitriou.<br />
On the complexity of the parity argument and other inefficient proofs of existence,<br />
<i>Journal of Computer and System Sciences</i> 48(3):498-532, 1994.<br />
<br />
{{Reference<br />
|tag=Per07<br />
|authors=K. Pervyshev<br />
|title=On heuristic time hierarchies<br />
|journal=Proceedings of the 22nd Annual IEEE Conference on Computational Complexity<br />
|srcdetail=347-357, 2007<br />
}}<br />
<br />
<span id="pos44" style="color:maroon">[Pos44]</span><br />
E. L. Post.<br />
Recursively enumerable sets of positive integers and their decision problems,<br />
<i>Bulletin of the American Mathematical Society</i> 50:284-316, 1944.<br />
<br />
<span id="pp00" style="color:maroon">[PP00]</span><br />
S. Parker and M. B. Plenio.<br />
Efficient factorization with a single pure qubit and log N mixed qubits,<br />
<i>Physical Review Letters</i> 85:3049, 2000.<br />
arXiv:[http://arxiv.org/abs/quant-ph/0001066 quant-ph/0001066].<br />
<br />
<span id="pps83" style="color:maroon">[PPS+83]</span><br />
W. J. Paul, N. Pippenger, E. Szemer&eacute;di, and W. T. Trotter.<br />
On determinism versus nondeterminism and related problems,<br />
<i>Proceedings of IEEE FOCS'83</i>, pp. 429-438, 1983.<br />
<br />
<span id="pra74" style="color:maroon">[Pra74]</span><br />
V. R. Pratt.<br />
The power of negative thinking in multiplying Boolean matrices,<br />
<i>STOC '74: Proceedings of the sixth annual ACM Symposium on Theory of Computing</i>, 80-83, 1974.<br />
<br />
<span id="pra75" style="color:maroon">[Pra75]</span><br />
V. R. Pratt.<br />
Every prime has a succinct certificate,<br />
<i>SIAM Journal on Computing</i>, 4:214-220, 1975.<br />
<br />
<span id="pv04" style="color:maroon">[PV04]</span><br />
A. Pavan and N. V. Vinodchandran.<br />
[http://ftp.eccc.uni-trier.de/eccc-reports/2004/TR04-053/ TR04-053].<br />
<br />
<span id="py84" style="color:maroon">[PY84]</span><br />
C. H. Papadimitriou and M. Yannakakis.<br />
The complexity of facets (and some facets of complexity),<br />
<i>Journal of Computer and System Sciences</i> 28:244-259, 1984.<br />
<br />
<span id="py88" style="color:maroon">[PY88]</span><br />
C. H. Papadimitriou and M. Yannakakis.<br />
Optimization, approximation, and complexity classes,<br />
<i>Proceedings of ACM STOC'88</i>, pp. 229-234, 1988.<br />
<br />
<span id="py96" style="color:maroon">[PY96]</span><br />
C. H. Papadimitriou and M. Yannakakis.<br />
On limited nondeterminism and the complexity of the VC dimension,<br />
<i>Journal of Computer and System Sciences</i> 53(2):161-170, 1996.<br />
<br />
<span id="pz83" style="color:maroon">[PZ83]</span><br />
C. H. Papadimitriou and S. Zachos.<br />
Two remarks on the power of counting,<br />
<i>Proceedings of the 6th GI Conference in Theoretical Computer Science</i>, Lecture Notes in Computer Science Vol. 145, Springer-Verlag, pp. 269-276, 1983.<br />
<br />
===== R =====<br />
<br />
<span id="ra00" style="color:maroon">[RA00]</span><br />
K. Reinhardt and E. Allender.<br />
Making nondeterminism unambiguous,<br />
<i>SIAM Journal on Computing</i> 29:1118-1131, 2000.<br />
ECCC [http://eccc.uni-trier.de/eccc-reports/1997/TR97-014/ TR97-014],<br />
DIMACS [http://dimacs.rutgers.edu/TechnicalReports/abstracts/1997/97-46.html TR 97-46].<br />
<br />
<span id="rab60" style="color:maroon">[Rab60]</span><br />
M. O. Rabin.<br />
Degree of difficulty of computing a function and a partial ordering of recursive sets,<br />
Tech Report No. 2, Hebrew University, 1960.<br />
<br />
<span id="rac82" style="color:maroon">[Rac82]</span><br />
C. Rackoff.<br />
Relativized questions involving probabilistic algorithms,<br />
<i>Journal of the ACM</i> 29(1):261-268, 1982.<br />
<br />
<span id="raz05" style="color:maroon">[Raz05]</span><br />
R. Raz.<br />
Quantum information and the PCP theorem,<br />
to appear in <i>Proc. IEEE FOCS</i>, 2005.<br />
ECCC [http://www.eccc.uni-trier.de/eccc-reports/2005/TR05-038/index.html TR05-038].<br />
<br />
<span id="raz85" style="color:maroon">[Raz85]</span><br />
A. A. Razborov.<br />
Lower bounds on the monotone complexity of some Boolean functions,<br />
<i>Dokl. Akad. Nauk SSSR</i> 281(4):798-801, 1985.<br />
English translation in <i>Soviet Math. Dokl.</i> 31:354-357, 1985.<br />
<br />
<span id="raz85b" style="color:maroon">[Raz85b]</span><br />
A. A. Razborov.<br />
A lower bound on the monotone network complexity of the logical permanent,<br />
<i>Mat. Zametky</i> 37(6):887-900, 1985.<br />
English translation in <i>Russian Mathematical Notes</i> 37:485-493, 1985.<br />
<br />
<span id="raz87" style="color:maroon">[Raz87]</span><br />
A. A. Razborov.<br />
Lower bounds for the size of circuits of bounded depth with basis {&amp;,},<br />
<i>Mathematicheskie Zametki</i> 41(4):598-607, 1987.<br />
English translation in <i>Math. Notes. USSR</i> 41(4):333-338, 1987.<br />
<br />
<span id="raz94" style="color:maroon">[Raz94]</span><br />
A. A. Razborov.<br />
On provably disjoint NP-pairs,<br />
ECCC [http://eccc.uni-trier.de/eccc-reports/1994/TR94-006/ TR94-006], 1994.<br />
<br />
<span id="reg02" style="color:maroon">[Reg02]</span><br />
K. Regan.<br />
Understanding the Mulmuley-Sohoni approach to P vs. NP,<br />
<i>Bulletin of the EATCS</i> 78, October 2002.<br />
[http://people.cs.uchicago.edu/~fortnow/beatcs/column78.pdf http://people.cs.uchicago.edu/~fortnow/beatcs/column78.pdf].<br />
<br />
<span id="rei04" style="color:maroon">[Rei04]</span><br />
O. Reingold.<br />
Undirected st-connectivity in log-space,<br />
ECCC [http://eccc.uni-trier.de/eccc-reports/2004/TR04-094/ TR04-094], 2004.<br />
<br />
<span id="rr95" style="color:maroon">[RR95]</span><br />
K. Regan, J. Royer.<br />
On Closure Properties of Bounded two-Sided Error Complexity Classes,<br />
Math. Systems Theory, 28 (1995) 229-243.<br />
ftp://ftp.cis.syr.edu/users/royer/coinflips.ps<br />
<br />
<span id="rr97" style="color:maroon">[RR97]</span><br />
A. A. Razborov and S. Rudich.<br />
Natural proofs,<br />
<i>Journal of Computer and System Sciences</i> 55(1):24-35, 1997.<br />
ECCC [http://eccc.uni-trier.de/eccc-reports/1994/TR94-010/ TR94-010].<br />
<br />
<span id="rs98" style="color:maroon">[RS98]</span><br />
A. Russell and R. Sundaram.<br />
Symmetric alternation captures BPP,<br />
<i>Computational Complexity</i> 7(2):152-162, 1998.<br />
<br />
<span id="rtv05" style="color:maroon">[RTV05]</span><br />
O. Reingold and L. Trevisan and S. Vadhan.<br />
Pseudorandom walks in biregular graphs and the RL vs. L problem,<br />
ECCC [http://eccc.uni-trier.de/eccc-reports/2005/TR05-022/ TR05-022], 2004.<br />
<br />
<span id="rub88" style="color:maroon">[Rub88]</span><br />
R. Rubinstein.<br />
<i>Structural Complexity Classes of Sparse Sets: Intractability, Data Compression, and Printability</i>,<br />
PhD Thesis, Northeastern University (Boston, MA), 1988.<br />
<br />
<span id="rud97" style="color:maroon">[Rud97]</span><br />
S. Rudich.<br />
Super-bits, demi-bits, and NP/qpoly-natural proofs,<br />
<i>RANDOM: International Workshop on Randomization and Approximation Techniques in Computer Science</i>, Lecture Notes in Computer Science, Springer-Verlag, 1997.<br />
<br />
<span id="rus85" style="color:maroon">[Rus85]</span><br />
D. A. Russo.<br />
Structural Properties of Complexity Classes.<br />
PhD thesis, UC Santa Barbara, 1985.<br />
<br />
<span id="ruv12" style="color:maroon">[RUV12]</span><br />
Ben W. Reichardt, Falk Unger, Umesh Vazirani.<br />
A classical leash for a quantum system: Command of quantum systems via rigidity of CHSH games,<br />
<i>Nature</i> 496:456–460, 2013.<br />
<br />
<span id="ruz81" style="color:maroon">[Ruz81]</span><br />
W. L. Ruzzo.<br />
On uniform circuit complexity,<br />
<i>Journal of Computer and System Sciences</i> 22(3):365-383, 1971.<br />
<br />
<span id="rw01" style="color:maroon">[RW01]</span><br />
S. Reith and K. Wagner.<br />
On Boolean lowness and Boolean highness,<br />
<i>Theoretical Computer Science</i> 261(2):305-321, 2001.<br />
<br />
===== S =====<br />
<br />
{{Reference<br />
|tag=San07<br />
|title=Circuit lower bounds for Merlin-Arthur classes<br />
|journal=Electronic Colloquium on Computational Complexity<br />
|authors=R. Santhanam<br />
|srcdetail=Report TR07-005<br />
}}<br />
<br />
<span id="sav70" style="color:maroon">[Sav70]</span><br />
W. Savitch.<br />
Relationships between nondeterministic and deterministic tape complexities,<br />
<i>Journal of Computer and System Sciences</i> 4(2):177-192, 1970.<br />
<br />
<span id="sch02a" style="color:maroon">[Sch02a]</span><br />
M. Schaefer and C. Umans.<br />
Completeness in the Polynomial-Time Hierarchy: A Compendium,<br />
<i>Sigact News</i> September, 2002.<br />
<br />
<span id="sch02b" style="color:maroon">[Sch02b]</span><br />
M. Schaefer and C. Umans.<br />
Completeness in the Polynomial-Time Hierarchy: Part II,<br />
<i>Sigact News</i> December, 2002.<br />
<br />
<span id="sch03" style="color:maroon">[Sch03]</span><br />
P. Schnoebelen.<br />
Oracle circuits for branching-time model checking,<br />
<i>Proceedings of ICALP 2003</i>, pp. 790-801, 2003.<br />
<br />
<span id="sch78" style="color:maroon">[Sch78]</span><br />
C. P. Schnorr.<br />
Satisfiability Is Quasilinear Complete in NQL,<br />
<i>Journal of the ACM</i> 25(1):136-145, 1978.<br />
<br />
<span id="sch83" style="color:maroon">[Sch83]</span><br />
U. Sch&ouml;ning.<br />
A low and a high hierarchy within NP,<br />
<i>Journal of Computer and System Sciences</i> 27:14-28, 1983.<br />
<br />
<span id="sch86" style="color:maroon">[Sch86]</span><br />
U. Sch&ouml;ning.<br />
Complete Sets and Closeness to Complexity Classes,<br />
<i>Mathematical Systems Theory</i> 19:29-41, 1986.<br />
DOI:[http://dx.doi.org/10.1007/BF01704904 10.1007/BF01704904]<br />
<br />
<span id="sel79" style="color:maroon">[Sel79]</span><br />
A. Selman.<br />
P-selective sets, tally languages, and the behavior of polynomial time reducibilities in NP,<br />
<i>Mathematical Systems Theory</i> 13(1):55-65, 1979.<br />
<br />
<span id="ses05" style="color:maroon">[SES05]</span><br />
Eric Allender, Samir Datta, and Sambuddha Roy.<br />
The directed planar reachability problem,<br />
<i>Proceedings of FSTTCS</i>, #1373 in Computer Science<br />
<br />
<span id="sf98" style="color:maroon">[SF98]</span><br />
H. T. Siegelmann and S. Fishman.<br />
Analog computation with dynamical systems,<br />
Physica 120D, p. 214, 1998.<br />
<br />
<span id="sfm78" style="color:maroon">[SFM78]</span><br />
J. Seiferas, M. Fischer, and A. Meyer.<br />
Separating nondeterministic time complexity classes,<br />
<i>Journal of the ACM</i> 25:146-167, 1978.<br />
<br />
<span id="sha90" style="color:maroon">[Sha90]</span><br />
A. Shamir.<br />
IP=PSPACE,<br />
<i>Proceedings of IEEE FOCS'90</i>, pp. 11-15, 1990.<br />
<br />
<span id="she59" style="color:maroon">[She59]</span><br />
J. C. Shepherdson.<br />
The reduction of two-way automata to one-way automata,<br />
<i>IBM Journal of Research and Development</i>, 3:198-200, 1959.<br />
<br />
<span id="she08" style="color:maroon">[She08]</span><br />
A. A. Sherstov.<br />
Separating AC<sup>0</sup> from depth-2 majority circuits,<br />
<i>Computational Complexity</i>, 17(2):149-178, 2008.<br />
[http://www.cs.utexas.edu/~sherstov/publications/pdf/cc08hsmat.pdf http://www.cs.utexas.edu/~sherstov/publications/pdf/cc08hsmat.pdf]<br />
<br />
<span id="shi03" style="color:maroon">[Shi03]</span><br />
Y. Shi.<br />
Quantum and classical tradeoffs,<br />
arXiv:[http://arxiv.org/abs/quant-ph/0312213 quant-ph/0312213],<br />
ECCC [http://eccc.uni-trier.de/eccc-reports/2004/TR04-023/ TR04-023], 2003.<br />
<br />
<span id="sho97" style="color:maroon">[Sho97]</span><br />
P. Shor.<br />
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer,<br />
<i>SIAM Journal on Computing</i> 26(5):1484-1509, 1997.<br />
arXiv:[http://arxiv.org/abs/quant-ph/9508027 quant-ph/9508027].<br />
<br />
<span id="sho99" style="color:maroon">[Sho99]</span><br />
R. A. Shore.<br />
The recursively enumerable degrees,<br />
<i>Handbook of Recursion Theory</i> (E. Griffor, ed.), pp. 169-197, North-Holland, Amsterdam, 1999.<br />
<br />
<span id="sip82" style="color:maroon">[Sip82]</span><br />
M. Sipser.<br />
On relativization and the existence of complete sets,<br />
<i>Proceedings of ICALP'82</i>, Springer-Verlag Lecture Notes in Computer Science volume 140, pp. 523-531, 1982.<br />
<br />
<span id="sip92" style="color:maroon">[Sip92]</span><br />
M. Sipser.<br />
The history and status of the P versus NP question,<br />
<i>Proceedings of ACM STOC'92</i>, pp. 603-618, 1992.<br />
<br />
<span id="sm02" style="color:maroon">[SM02]</span><br />
L. J. Stockmeyer and A. R. Meyer.<br />
Cosmological lower bound on the circuit complexity of a small problem in logic,<br />
<i>Journal of the ACM</i> 49(6):753-784, 2002.<br />
[http://theory.lcs.mit.edu/~meyer/stock-circuit-jacm.pdf http://theory.lcs.mit.edu/~meyer/stock-circuit-jacm.pdf].<br />
<br />
{{Reference<br />
|tag=SM03<br />
|authors=R. Santhanam, D. Melkebeek<br />
|title=Holographic proofs and derandomization<br />
|journal=Proceedings of the 18th Annual IEEE Conference on Computational Complexity<br />
|srcdetail=269-283<br />
}}<br />
<br />
<span id="smo87" style="color:maroon">[Smo87]</span><br />
R. Smolensky.<br />
Algebraic methods in the theory of lower bounds for Boolean circuit complexity,<br />
<i>Proceedings of ACM STOC'87</i>, pp. 77-82, 1987.<br />
<br />
<span id="sp98" style="color:maroon">[SP98]</span><br />
U. Sch&ouml;ning and R. Pruim.<br />
<i>Gems of Theoretical Computer Science</i>,<br />
Springer-Verlag, 1998.<br />
<br />
<span id="spa02" style="color:maroon">[Spa02]</span><br />
R. &#352;palek.<br />
Quantum circuits with unbounded fan-out,<br />
arXiv:[http://arxiv.org/abs/quant-ph/0208043 quant-ph/0208043], 2002.<br />
<br />
<span id="ss04" style="color:maroon">[SS04]</span><br />
A. Selman and S. Sengupta.<br />
Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchy,<br />
<i>Proceedings of IEEE Complexity 2004</i>, pp. 82-90, 2004.<br />
ECCC [http://eccc.uni-trier.de/eccc-reports/2004/TR04-007/ TR04-007].<br />
<br />
<span id="ss77" style="color:maroon">[SS77]</span><br />
R. Solovay and V. Strassen.<br />
A fast Monte-Carlo test for primality,<br />
<i>SIAM Journal on Computing</i>, 6:84-86, 1977.<br />
<br />
<span id="sto76" style="color:maroon">[Sto76]</span><br />
L. J. Stockmeyer.<br />
The polynomial hierarchy,<br />
<i>Theoretical Computer Science</i> 3:1-22, 1976.<br />
<br />
<span id="sto85" style="color:maroon">[Sto85]</span><br />
L. J. Stockmeyer.<br />
On approximation algorithms for #P,<br />
<i>SIAM Journal on Computing</i> 14:849-861, 1985.<br />
<br />
<span id="stt05" style="color:maroon">[STT05]</span><br />
Holger Spakowski, Mayur Thakur, and Rahul Tripathi.<br />
Quantum and Classical Complexity Classes: Separations, Collapses, and Closure Properties,<br />
Inform. and Comput. 200 (2005), no. 1, 1--34.<br />
[http://web.umr.edu/~thakurk/publications/quantum-j.pdf http://web.umr.edu/~thakurk/publications/quantum-j.pdf]<br />
<br />
<span id="su05" style="color:maroon">[SU05]</span><br />
R. Shaltiel and C. Umans.<br />
Pseudorandomness for approximate counting and sampling,<br />
<i>Proceedings of IEEE Complexity'2005</i>, pp. 212-226, 2005.<br />
[http://www.cs.haifa.ac.il/~ronen/online_papers/derand-ccc-final.ps http://www.cs.haifa.ac.il/~ronen/online_papers/derand-ccc-final.ps].<br />
<br />
<span id="sub94" style="color:maroon">[Sub94]</span><br />
A. Subramanian. <br />
A New Approach to Stable Matching Problems, <br />
<i>SIAM Journal on Computing</i> 23(4), 671-701, 1994. <br />
<br />
<span id="sud78" style="color:maroon">[Sud78]</span><br />
I. Sudborough.<br />
On the tape complexity of deterministic context-free languages,<br />
<i>Journal of the ACM</i> 25(3):405-414, 1978.<br />
<br />
<span id="sv97" style="color:maroon">[SV97]</span><br />
A. Sahai and S. Vadhan.<br />
A complete promise problem for statistical zero-knowledge,<br />
<i>Proceedings of IEEE FOCS'97</i>.<br />
[http://www.eecs.harvard.edu/~salil/papers/complete-abs.html http://www.eecs.harvard.edu/~salil/papers/complete-abs.html].<br />
<br />
<span id="sz95" style="color:maroon">[SZ95]</span><br />
M. Saks and S. Zhou.<br />
RSPACE(s) is contained in DSPACE(s<sup>3/2</sup>),<br />
<i>Proceedings of IEEE FOCS'95</i>, pp. 344-353, 1995.<br />
<br />
<span id="sze87" style="color:maroon">[Sze87]</span><br />
R. Szelepcs&eacute;nyi.<br />
The method of forcing for nondeterministic automata,<br />
<i>Bulletin of the EATCS</i> 33:96-100, 1987.<br />
<br />
{{Reference<br />
|id="szep94" |tag=Szep94<br />
|title=Turing Machines With Sublogarithmic Space<br />
|journal=Lecture Notes in Computer Science<br />
|authors=Andrzej Szepietowski<br />
|srcdetail=volume 843<br />
}}<br />
<br />
===== T =====<br />
<br />
<span id="tan07" style="color:maroon">[Tan07]</span><br />
T. Tantau.<br />
Logspace Optimization Problems and Their Approximability Properties,<br />
<i>Theory of Computing Systems</i>, 41:327-350, 2007.<br />
<br />
<span id="tar88" style="color:maroon">[Tar88]</span><br />
E. Tardos.<br />
The gap between monotone and non-monotone circuit complexity is exponential,<br />
<i>Combinatorica</i>, 8:141-142, 1988.<br />
<br />
<span id="tar89" style="color:maroon">[Tar89]</span><br />
G. Tardos.<br />
Query complexity, or why is it difficult to separate NP<sup>A</sup> intersect coNP<sup>A</sup> from P<sup>A</sup> by random oracles A,<br />
<i>Combinatorica</i>, 9:385-392, 1989.<br />
<br />
<span id="tha98" style="color:maroon">[Tha98]</span><br />
J. S. Thathachar.<br />
On Separating the Read-k-Times Branching Program Hierarchy,<br />
<i>Proceedings of the 30th ACM Symposium on Theory of Computing</i>, pp. 653-662, 1998.<br />
ECCC [http://eccc.hpi-web.de/eccc-reports/1998/TR98-002/ TR98-02], DOI:[http://doi.acm.org/10.1145/276698.276881 10.1145/276698.276881].<br />
<br />
<span id="tod89" style="color:maroon">[Tod89]</span><br />
S. Toda.<br />
On the computational power of PP and P,<br />
<i>Proceedings of IEEE FOCS'89</i>, pp. 514-519, 1989.<br />
<br />
<span id="tor00" style="color:maroon">[Tor00]</span><br />
J. Tor&aacute;n.<br />
On the hardness of graph isomorphism,<br />
<i>Proceedings of IEEE FOCS'2000</i>, pp. 180-186, 2000.<br />
<br />
<span id="tor88" style="color:maroon">[Tor88]</span><br />
J. Tor\'an.<br />
Structural Properties of the Counting Hierarchies,<br />
Ph.D Theis, 1988.<br />
<br />
<span id="tor90" style="color:maroon">[Tor90]</span><br />
J. Tor&aacute;n.<br />
Counting the number of solutions,<br />
<i>Proceedings of 15th Conference on Mathematical Foundations of Computer Science (MFCS)</i>, pp. 121-135, Springer-Verlag Lecture Notes in Computer Science 452, 1990.<br />
<br />
<span id="tor91" style="color:maroon">[Tor91]</span><br />
J. Tor&aacute;n.<br />
Complexity classes defined by counting quantifiers,<br />
<i>Journal of the ACM</i> 38:753-774, 1991.<br />
<br />
<span id="tur36" style="color:maroon">[Tur36]</span><br />
A. M. Turing.<br />
On computable numbers, with an application to the <i>Entscheidungsproblem</i>,<br />
<i>Proceedings of the London Mathematical Society</i> 2(42):230-265, 1936; 2(43):544-546, 1937.<br />
<br />
<span id="tv02" style="color:maroon">[TV02]</span><br />
L. Trevisan and S. Vadhan.<br />
Pseudorandomness and average-case complexity via uniform reductions,<br />
<i>Proceedings of CCC'2002</i>, pp. 129-138, 2002.<br />
<br />
===== U =====<br />
<br />
<span id="uma98" style="color:maroon">[Uma98]</span><br />
C. Umans.<br />
The minimum equivalent DNF problem and shortest implicants,<br />
<i>Proceedings of IEEE FOCS'98</i>, pp. 556-563, 1998.<br />
<br />
===== V =====<br />
<br />
<span id="vad06" style="color:maroon">[Vad06]</span><br />
S. Vadhan.<br />
An Unconditional Study of Computational Zero Knowledge,<br />
ECCC [http://eccc.hpi-web.de/eccc-reports/2006/TR06-056/ TR06-056].<br />
<br />
<span id="val03" style="color:maroon">[Val03]</span><br />
L. G. Valiant.<br />
Three problems in computer science,<br />
<i>Journal of the ACM</i> 50(1):96-99, 2003.<br />
<br />
<span id="val76" style="color:maroon">[Val76]</span><br />
L. G. Valiant.<br />
Relative complexity of checking and evaluating,<br />
<i>Information Processing Letters</i>, 5:20-23, 1976.<br />
<br />
<span id="val79" style="color:maroon">[Val79]</span><br />
L. G. Valiant.<br />
The complexity of computing the permanent,<br />
<i>Theoretical Computer Science</i>, 8:189-201, 1979.<br />
<br />
<span id="val79b" style="color:maroon">[Val79b]</span><br />
L. G. Valiant.<br />
Completeness classes in algebra,<br />
<i>Proceedings of ACM STOC'79</i>, pp. 249-261, 1979.<br />
<br />
<span id="var82" style="color:maroon">[Var82]</span><br />
M. Vardi.<br />
Complexity of relational query languages,<br />
<i>Proceedings of ACM STOC'82</i>, pp. 137-146, 1982.<br />
<br />
<span id="ven91" style="color:maroon">[Ven91]</span><br />
H. Venkateswaran.<br />
Properties that characterize LOGCFL,<br />
<i>Journal of Computer and System Sciences</i> 43(2):380-404, 1991.<br />
<br />
<span id="ver92" style="color:maroon">[Ver92]</span><br />
N. K. Vereshchagin.<br />
On the power of PP,<br />
<i>Proceedings of IEEE Complexity'92</i>, pp. 138-143, 1992.<br />
<br />
<span id="ver95" style="color:maroon">[Ver95]</span><br />
N. K. Vereshchagin.<br />
Oracle separation of complexity classes and lower bounds for perceptrons solving separation problems,<br />
<i>Izvestiya Mathematics</i> 59(6):1103-1122, 1995.<br />
<br />
<span id="vid03" style="color:maroon">[Vid03]</span><br />
G. Vidal.<br />
Efficient classical simulation of slightly entangled quantum computations,<br />
<i>Physical Review Letters</i> 91:147902, 2003.<br />
arXiv:[http://arxiv.org/abs/quant-ph/0301063 quant-ph/0301063].<br />
<br />
<span id="vin04" style="color:maroon">[Vin04]</span><br />
N. V. Vinodchandran.<br />
Counting complexity of solvable group problems,<br />
<i>SIAM Journal on Computing</i> 33(4):852-869, 2004,<br />
[http://www.cse.unl.edu/~vinod/papers/SIAMFinal.ps http://www.cse.unl.edu/~vinod/papers/SIAMFinal.ps].<br />
<br />
<span id="vin04b" style="color:maroon">[Vin04b]</span><br />
N. V. Vinodchandran.<br />
A note on the circuit complexity of PP,<br />
ECCC [http://eccc.uni-trier.de/eccc-reports/2004/TR04-056/ TR04-056], 2004.<br />
<br />
<span id="vsb83" style="color:maroon">[VSB+83]</span><br />
L. G. Valiant, S. Skyum, S. Berkowitz, and C. Rackoff.<br />
Fast parallel computation of polynomials using few processors,<br />
<i>SIAM Journal on Computing</i> 12(4):641-644, 1983.<br />
<br />
<span id="vv85" style="color:maroon">[VV85]</span><br />
U. V. Vazirani and V. V. Vazirani.<br />
Random polynomial time equals semi-random polynomial time,<br />
<i>Proceedings of IEEE FOCS'85</i>, pp. 417-428, 1985.<br />
<br />
<span id="vv86" style="color:maroon">[VV86]</span><br />
L. G. Valiant and V. V. Vazirani.<br />
NP is as easy as detecting unique solutions,<br />
<i>Theoretical Computer Science</i> 47(3):85-93, 1986.<br />
<br />
<span id="vya03" style="color:maroon">[Vya03]</span><br />
M. Vyalyi.<br />
QMA=PP implies that PP contains PH,<br />
ECCC [http://eccc.uni-trier.de/eccc-reports/2003/TR03-021/ TR03-021], 2003.<br />
<br />
===== W =====<br />
<br />
<span id="wag86" style="color:maroon">[Wag86]</span><br />
K. W. Wagner.<br />
The complexity of combinatorial problems with succinct input representation,<br />
<i>Acta Informatica</i> 23:325-356, 1986.<br />
<br />
<span id="wag88" style="color:maroon">[Wag88]</span><br />
K. W. Wagner.<br />
Bounded query computation,<br />
<i>Proceedings of IEEE Complexity'88</i>, pp. 260-277, 1988.<br />
<br />
<span id="ww85" style="color:maroon">[WW85]</span><br />
G. Wechsung.<br />
On the Boolean closure of NP,<br />
<i>Proceedings of the International Conference on Fundamentals of Computation Theory</i>, LNCS volume 199, Springer-Verlag, pp. 485-493.<br />
<br />
<span id="wat00" style="color:maroon">[Wat00]</span><br />
J. Watrous.<br />
Succinct quantum proofs for properties of finite groups,<br />
<i>Proceedings of IEEE FOCS'2000</i>, pp. 537-546, 2000.<br />
arXiv:[http://arxiv.org/abs/cs.CC/0009002 cs.CC/0009002].<br />
<br />
<span id="wat02" style="color:maroon">[Wat02]</span><br />
J. Watrous.<br />
Limits on the power of quantum statistical zero-knowledge,<br />
to appear in <i>Proceedings of IEEE FOCS'2002</i>.<br />
arXiv:[http://arxiv.org/abs/quant-ph/0202111 quant-ph/0202111].<br />
<br />
<span id="wat09" style="color:maroon">[Wat09]</span><br />
J. Watrous.<br />
Quantum Computational Complexity, <i>Encyclopedia of Complexity and Systems Science</i>, Springer, pp. 7174-7201, 2009.<br />
arXiv:[http://arxiv.org/abs/0804.3401 quant-ph/0804.3401].<br />
<br />
<span id="wat87" style="color:maroon">[Wat87]</span><br />
O. Watanabe.<br />
Comparison of polynomial time completeness notions,<br />
<i>Theoretical Computer Science</i> 53:249-265, 1987.<br />
<br />
<span id="wat99" style="color:maroon">[Wat99]</span><br />
J. Watrous.<br />
PSPACE has constant-round quantum interactive proof systems,<br />
<i>Proceedings of IEEE FOCS'99</i>, pp. 112-119, 1999.<br />
arXiv:[http://arxiv.org/abs/cs.CC/9901015 cs.CC/9901015].<br />
<br />
<span id="wat99b" style="color:maroon">[Wat99b]</span><br />
J. Watrous.<br />
Space-bounded quantum complexity,<br />
<i>Journal of Computer and System Sciences</i> 59(2):281-326, 1999.<br />
[http://www.cpsc.ucalgary.ca/%7Ejwatrous/papers/jcss_space.ps http://www.cpsc.ucalgary.ca/%7Ejwatrous/papers/jcss_space.ps].<br />
<br />
<span id="weg87" style="color:maroon">[Weg87]</span><br />
I. Wegener.<br />
The Complexity of Boolean Functions, New York: Wiley 1987.<br />
<br />
<span id="weg88" style="color:maroon">[Weg88]</span><br />
I. Wegener.<br />
On the Complexity of Branching Programs and Decision Trees for Clique Functions,<br />
<i>Journal of the ACM</i> 35(2):461-471, 1988.<br />
DOI:[http://doi.acm.org/10.1145/42282.46161 10.1145/42282.46161].<br />
<br />
<span id="weh06" style="color:maroon">[Weh06]</span><br />
S. Wehner.<br />
Entanglement in interactive proof systems with binary answers. In <i>Proceedings of<br />
the 23rd Annual Symposium on Theoretical Aspects of Computer Science</i>, volume 3884 of <i>Lecture<br />
Notes in Computer Science</i>, pages 162–171. Springer, 2006<br />
<br />
<span id="wig06" style="color:maroon">[Wig06]</span><br />
A. Wigderson<br />
P, NP, and mathematics--a computational complexity perspective, 2006 mimeo.<br />
[www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/W06/W06.pdf].<br />
<br />
<span id="wil85" style="color:maroon">[Wil85]</span><br />
C. Wilson.<br />
Relativized circuit complexity,<br />
<i>Journal of Computer and System Sciences</i> 31:169-181, 1985.<br />
<br />
<span id="wil11" style="color:maroon">[Wil11]</span><br />
R. Williams. Non-uniform ACC circuit lower bounds.<br />
<i>To appear in IEEE Conference<br />
on Computational Complexity</i> 2011.<br />
<br />
<span id="wol94" style="color: maroon;">[Wol94]</span><br />
Marty J. Wolf.<br />
Nondeterministic circuits, space complexity and quasigroups.<br />
<i>Theoretical Computer Science</i> 125:295–313, 1994.<br />
<br />
===== Y =====<br />
<br />
{{Reference<br />
|tag=Yap83<br />
|authors=C. Yap<br />
|title=Some consequences of non-uniform conditions on uniform classes<br />
|journal=Theoretical Computer Science<br />
|srcdetail=(1983), 26, 287-300<br />
}}<br />
<br />
<span id="yam99" style="color:maroon">[Yam99]</span><br />
T. Yamakami.<br />
Polynomial time samplable distributions,<br />
J. Complexity 15 (1999), no. 4, 557--574.<br />
ECCC [http://eccc.hpi-web.de/eccc-reports/1995/TR95-039/ TR95-039].<br />
<br />
<span id="yan81" style="color:maroon">[Yan81]</span><br />
M. Yannakakis.<br />
Algorithms for acyclic database schemas,<br />
<i>Proceedings of VLDB</i> (Very Large Databases), 1981.<br />
<br />
<span id="yao85" style="color:maroon">[Yao85]</span><br />
A. C.-C. Yao.<br />
Separating the polynomial hierarchy by oracles,<br />
<i>Proceedings of IEEE FOCS'85</i>, pp. 1-10, 1985.<br />
<br />
<span id="yao89" style="color:maroon">[Yao89]</span><br />
A. C.-C. Yao.<br />
Circuits and local computation,<br />
<i>Proceedings of ACM STOC'89</i>, pp. 186-196, 1989.<br />
<br />
<span id="yao90" style="color:maroon">[Yao90]</span><br />
A. C.-C. Yao.<br />
On ACC and threshold circuits,<br />
<i>Proceedings of IEEE FOCS'90</i>, pp. 619-627, 1990.<br />
<br />
<span id="yao90b" style="color:maroon">[Yao90b]</span><br />
A. C.-C. Yao.<br />
Coherent functions and program checkers,<br />
<i>Proceedings of ACM STOC'90</i>, 1990.<br />
<br />
<span id="yao93" style="color:maroon">[Yao93]</span><br />
A. C.-C. Yao.<br />
Quantum circuit complexity,<br />
<i>Proceedings of IEEE FOCS'93</i>, pp. 352-361, 1993.<br />
<br />
<span id="yes83" style="color:maroon">[Yes83]</span><br />
Y. Yesha.<br />
On certain polynomial-time truth-table reducibilities of complete sets to sparse sets,<br />
<i>SIAM Journal on Computing</i>, 12(3):411-425, 1983.<br />
DOI:[http://dx.doi.org/10.1137/0212027 10.1137/0212027]<br />
<br />
===== Z =====<br />
<br />
<span id="zac88" style="color:maroon">[Zac88]</span><br />
S. Zachos.<br />
Probabilistic quantifiers and games,<br />
<i>Journal of Computer and System Sciences</i> 36(3):433-451, 1988.<br />
<br />
<span id="zh86" style="color:maroon">[ZH86]</span><br />
S. Zachos and H. Heller.<br />
A decisive characterization of BPP.<br />
''Information and Control'', 69(1&ndash;3):125&ndash;135, 1986.<br />
<br />
<span id="zuc91" style="color:maroon">[Zuc91]</span><br />
D. Zuckerman.<br />
Simulating BPP using a general weak random source,<br />
<i>Algorithmica</i> 16 (1996), no. 4-5, 367--391<br />
[http://www.cs.utexas.edu/users/diz/pubs/bpp.ps http://www.cs.utexas.edu/users/diz/pubs/bpp.ps].<br />
<br />
[[Category:Computational Complexity]]</div>JumpDisconthttps://complexityzoo.net/index.php?title=Complexity_Zoo:U&diff=6326Complexity Zoo:U2015-07-04T11:49:50Z<p>JumpDiscont: /* UCC: Unique Connected Component */ added more recent result</p>
<hr />
<div>__NOTOC__<br />
{{CZ-Letter-Menu|U}}<br />
<br />
<br />
===== <span id="uap" style="color:red">UAP</span>: Unambiguous Alternating Polynomial-Time =====<br />
Same as [[Complexity Zoo:A#ap|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.<br />
<br />
Contains [[#up|UP]].<br />
<br />
Defined in [[zooref#nr98|[NR98]]], where it was also shown that, even though [[Complexity Zoo:A#ap|AP]] = [[Complexity Zoo:P#pspace|PSPACE]], it is unlikely that the same is true for UAP, since UAP is contained in [[Complexity Zoo:S#spp|SPP]].<br />
<br />
[[zooref#cgr04|[CGR+04]]] have also shown that UAP<sup>UAP</sup> = UAP, and that UAP contains [[Complexity_Garden#graph_isomorphism|Graph Isomorphism]] problem.<br />
<br />
----<br />
<br />
===== <span id="ucc" style="color:red">UCC</span>: Unique Connected Component =====<br />
The class of problems reducible in [[Complexity Zoo:L#l|L]] to the problem of whether an undirected graph has a unique connected component.<br />
<br />
See [[zooref#ag00|[AG00]]] for more information.<br />
<br />
Equals [[Complexity Zoo:L#l|L]]. [[zooref#rei00|[Rei04]]]<br />
<br />
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.<br />
<br />
----<br />
<br />
===== <span id="ucfl" style="color:red">UCFL</span>: Unambiguous [[Complexity Zoo:C#cfl|CFL]] =====<br />
<br />
The class of context-free languages which can be represented by grammars where each word in the language has exactly one leftmost derivation.<br />
<br />
Strictly contains [[Complexity Zoo:D#dcfl|Deterministic CFL]]. Strictly contained in [[Complexity Zoo:C#cfl|CFL]].<br />
<br />
----<br />
<br />
===== <span id="ul" style="color:red">UL</span>: Unambiguous [[Complexity Zoo:L#l|L]] =====<br />
Has the same relation to [[Complexity Zoo:L#l|L]] as [[#up|UP]] does to [[Complexity Zoo:P#p|P]].<br />
<br />
If UL = [[Complexity Zoo:N#nl|NL]], then [[Complexity Zoo:F#fnl|FNL]] is contained in [[Complexity Zoo:Symbols#sharpl|#L]] [[zooref#aj93|[AJ93]]].<br />
<br />
----<br />
===== <span id="ulpoly" style="color:red">UL/poly</span>: Nonuniform [[#ul|UL]] =====<br />
Has the same relation to [[#ul|UL]] as [[Complexity Zoo:P#ppoly|P/poly]] does to [[Complexity Zoo:P#p|P]].<br />
<br />
Equals [[Complexity Zoo:N#nlpoly|NL/poly]] [[zooref#ra00|[RA00]]]. (A corollary is that UL/poly is closed under complement).<br />
<br />
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]].<br />
<br />
----<br />
===== <span id="ue" style="color:red">UE</span>: Unambiguous Exponential-Time With Linear Exponent =====<br />
Has the same relation to [[Complexity Zoo:E#e|E]] as [[#up|UP]] does to [[Complexity Zoo:P#p|P]].<br />
<br />
----<br />
===== <span id="up" style="color:red">UP</span>: Unambiguous Polynomial-Time =====<br />
The class of decision problems solvable by an [[Complexity Zoo:N#np|NP]] machine such that<br />
<ol><br />
<li>If the answer is 'yes,' exactly one computation path accepts.</li><br />
<li>If the answer is 'no,' all computation paths reject.</li><br />
</ol><br />
Defined by [[zooref#val76|[Val76]]].<br />
<br />
"Worst-case" one-way functions exist if and only if [[Complexity Zoo:P#p|P]] does not equal UP ([[zooref#gs88|[GS88]]] and independently [[zooref#ko85|[Ko85]]]). "Worst-case" one-way permutations exist if and only if [[Complexity Zoo:P#p|P]] does not equal UP &#8745; [[Complexity Zoo:C#coup|coUP]] [[zooref#ht03|[HT03]]]. Note that these are weaker than the one-way functions and permutations that are needed for cryptographic applications.<br />
<br />
There exists an oracle relative to which [[Complexity Zoo:P#p|P]] is strictly contained in UP is strictly contained in [[Complexity Zoo:N#np|NP]] [[zooref#rac82|[Rac82]]]; indeed, these classes are distinct with probability 1 relative to a random oracle [[zooref#bei89|[Bei89]]].<br />
<br />
[[Complexity Zoo:N#np|NP]] is contained in [[Complexity Zoo:R#rp|RP]]<sup>[[Complexity Zoo:P#promiseup|PromiseUP]]</sup> [[zooref#vv86|[VV86]]]. On the other hand, [[zooref#bbf98|[BBF98]]] give an oracle relative to which [[Complexity Zoo:P#p|P]] = UP but still [[Complexity Zoo:P#p|P]] does not equal [[Complexity Zoo:N#np|NP]].<br />
<br />
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.<br />
<br />
----<br />
<br />
===== <span id="uppcc" style="color:red">UPP<sup>cc</sup></span>: Unrestricted Communication Analogue of [[Complexity Zoo:P#pp|PP]] =====<br />
Defined by [[zooref#bfs86|[BFS86]]], '''UPP<sup>cc</sup>''' is one of two communication complexity analogues of [[Complexity Zoo:P#pp|PP]].<br />
UPP<sup>cc</sup> is the class of all languages defined by functions <math>f : \{0,1\}^n \times \{0,1\}^n \to \{0,1\}</math> which are computable by polylogarithmic protocols that 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.<br />
<br />
''See also:'' [[Complexity Zoo:P#ppcc|PP<sup>cc</sup>]].<br />
<br />
----<br />
<br />
===== <span id="us" style="color:red">US</span>: Unique Polynomial-Time =====<br />
The all-American counting class.<br />
<br />
The class of decision problems solvable by an [[Complexity Zoo:N#np|NP]] machine such that the answer is 'yes' if and only if exactly one computation path accepts.<br />
<br />
In contrast to [[#up|UP]], a machine can legally have more than one accepting path - that just means that the corresponding input is not in the language.<br />
<br />
Defined in [[zooref#bg82|[BG82]]].<br />
<br />
Contains [[Complexity Zoo:C#conp|coNP]].</div>JumpDiscont