main.bbl
\begin{thebibliography}{BvdHL04}

\bibitem[BG98]{ban-gut:j:generalizations-of-tournaments-survey}
J.~{Bang-Jensen} and G.~Gutin.
\newblock Generalizations of tournaments: {A} survey.
\newblock {\em Journal of Graph Theory}, 28(4):171--202, 1998.

\bibitem[BvdHL04]{bar-hol-loe:j:multi-partite-graphs}
W.~Barrett, H.~van~der Holst, and R.~Loewy.
\newblock Graphs whose minimal rank is two.
\newblock {\em Electronic Journal of Linear Algebra}, 11:258--280, 2004.

\bibitem[For79]{for:j:sparse}
S.~Fortune.
\newblock A note on sparse complete sets.
\newblock {\em SIAM Journal on Computing}, 8(3):431--433, 1979.

\bibitem[Gut86]{gut:j:radii-tournaments}
G.~Gutin.
\newblock The radii of $n$-partite tournaments.
\newblock {\em Math.~Notes}, 40:414--417, 1986.

\bibitem[GW83]{gal-wig:j:succinct}
H.~Galperin and A.~Wigderson.
\newblock Succinct representations of graphs.
\newblock {\em Information and Control}, 56(3):183--198, 1983.

\bibitem[HC03]{cha-ho:j:strong-kings}
T.~Ho and J.~Chang.
\newblock Sorting a sequence of strong kings in a tournament.
\newblock {\em Information Processing Letters}, 87(6):317--320, 2003.

\bibitem[HHN04]{hem-hem-nic:j:associative-selectors-det-and-nondet}
L.~Hemaspaandra, H.~Hempel, and A.~Nickelsen.
\newblock Algebraic properties for selector functions.
\newblock {\em SIAM Journal on Computing}, 33(6):1309--1337, 2004.

\bibitem[HNP98]{hem-nas-par:j:linear-advice}
L.~Hemaspaandra, C.~Nasipak, and K.~Parkins.
\newblock A note on linear-nondeterminism, linear-sized, {K}arp--{L}ipton
  advice for the {P}-selective sets.
\newblock {\em Journal of Universal Computer Science}, 4(8):670--674, 1998.

\bibitem[HOZZ]{hem-ogi-zak-zim:jtoappearWITHconfPTR:psr-weak-P-rank}
L.~Hemaspaandra, M.~Ogihara, M.~Zaki, and M.~Zimand.
\newblock The complexity of finding top-{Toda}-equivalence-class
  members\typeout{MINOR PANIC: hem-ogi-zak-zim: Missing year/issue/voume, and
  remove To-appear}.
\newblock {\em Theory of Computing Systems}.
\newblock To appear. Preliminary version available in {\em Proceedings of 6th
  Latin American Symposium on Theoretical Informatics (Springer-Verlag, 2004)}.

\bibitem[HT96]{hem-tor:j:optimal-advice}
L.~Hemaspaandra and L.~Torenvliet.
\newblock Optimal advice.
\newblock {\em Theoretical Computer Science}, 154(2):367--377, 1996.

\bibitem[HT03]{hem-tor:b:semifeasible-computation}
L.~Hemaspaandra and L.~Torenvliet.
\newblock {\em Theory of Semi-Feasible Algorithms}.
\newblock Springer-Verlag, 2003.

\bibitem[HT05]{hem-tor:t:immunity}
L.~Hemaspaandra and L.~Torenvliet.
\newblock {P}-selectivity, immunity, and the power of one bit.
\newblock Technical Report TR-864, Department of Computer Science, University
  of Rochester, Rochester, NY, April 2005.

\bibitem[KF77]{fis-kin:cPARTIALLYOUTDATEDbyJ:preBETA}
C.~Kintala and P.~Fischer.
\newblock Computations with a restricted number of nondeterministic steps.
\newblock In {\em Proceedings of the 9th ACM Symposium on Theory of Computing},
  pages 178--185. ACM Press, May 1977.

\bibitem[KF80]{fis-kin:j:beta}
C.~Kintala and P.~Fisher.
\newblock Refining nondeterminism in relativized polynomial-time bounded
  computations.
\newblock {\em SIAM Journal on Computing}, 9(1):46--53, 1980.

\bibitem[KL80]{kar-lip:c:nonuniform}
R.~Karp and R.~Lipton.
\newblock Some connections between nonuniform and uniform complexity classes.
\newblock In {\em Proceedings of the 12th ACM Symposium on Theory of
  Computing}, pages 302--309. ACM Press, April 1980.
\newblock An extended version has also appeared as: Turing machines that take
  advice, {\em L'Enseignement Math\'{e}matique}, 2nd series, 28:191--209, 1982.

\bibitem[Ko83]{ko:j:self-reducibility}
K.~Ko.
\newblock On self-reducibility and weak {P}-selectivity.
\newblock {\em Journal of Computer and System Sciences}, 26(2):209--221, 1983.

\bibitem[Lan53]{lan:j:tournament-length-2}
H.~Landau.
\newblock On dominance relations and the structure of animal societies, {III}:
  {T}he condition for score structure.
\newblock {\em Bulletin of Mathematical Biophysics}, 15(2):143--148, 1953.

\bibitem[Lin92]{lin:c:circuit-uniformity}
S.~Lindell.
\newblock A purely logical characterization of circuit uniformity.
\newblock In {\em Proceedings of the 7th Structure in Complexity Theory
  Conference}, pages 185--192. IEEE Computer Society Press, June 1992.

\bibitem[Moo68]{moo:b:tournaments}
J.~Moon.
\newblock {\em Topics on Tournaments}.
\newblock Holt, Rinehart, and Winston, 1968.

\bibitem[MS72]{mey-sto:c:reg-exp-needs-exp-space}
A.~Meyer and L.~Stockmeyer.
\newblock The equivalence problem for regular expressions with squaring
  requires exponential space.
\newblock In {\em Proceedings of the 13th IEEE Symposium on Switching and
  Automata Theory}, pages 125--129, October 1972.

\bibitem[NT02]{nic-tan:c:reachability}
A.~Nickelsen and T.~Tantau.
\newblock On reachability in graphs with bounded independence number.
\newblock In {\em Proceedings of the 8th Annual International Computing and
  Combinatorics Conference}, volume 2387, pages 554--563. Springer-Verlag {\it
  Lecture Notes in Computer Science \#2387}, August 2002.

\bibitem[PT91]{pet-tho:j:kings-multipartite}
V.~Petrovic and C.~Thomassen.
\newblock Kings in $k$-partite tournaments\typeout{Minor panic: pet-tho:
  missing issue number}.
\newblock {\em Discrete Mathematics}, 98:237--238, 1991.

\bibitem[PY86]{pap-yan:j:succinct}
C.~Papadimitriou and M.~Yannakakis.
\newblock A note on succinct representations of graphs.
\newblock {\em Information and Control}, 71(3):181--185, 1986.

\bibitem[Sel79]{sel:j:pselective-tally}
A.~Selman.
\newblock {P}-selective sets, tally languages, and the behavior of polynomial
  time reducibilities on {N}{P}.
\newblock {\em Mathematical Systems Theory}, 13(1):55--65, 1979.

\bibitem[Sel81]{sel:j:some-observations-psel}
A.~Selman.
\newblock Some observations on {NP} real numbers and {P}-selective sets.
\newblock {\em Journal of Computer and System Sciences}, 23(3):326--332, 1981.

\bibitem[Sel82a]{sel:j:ana}
A.~Selman.
\newblock Analogues of semirecursive sets and effective reducibilities to the
  study of {N}{P} complexity.
\newblock {\em Information and Control}, 52(1):36--51, 1982.

\bibitem[Sel82b]{sel:j:reductions-pselective}
A.~Selman.
\newblock Reductions on {N}{P} and {P}-selective sets.
\newblock {\em Theoretical Computer Science}, 19(3):287--304, 1982.

\bibitem[SM73]{mey-sto:c:word-exponential}
L.~Stockmeyer and A.~Meyer.
\newblock Word problems requiring exponential time.
\newblock In {\em Proceedings of the 5th ACM Symposium on Theory of Computing},
  pages 1--9. ACM Press, 1973.

\bibitem[SSW03]{she-she-wu:j:sorted-kings-tournaments}
J.~Shen, L.~Sheng, and J.~Wu.
\newblock Searching for sorted sequences in tournaments.
\newblock {\em SIAM Journal on Computing}, 32(5):1201--1209, 2003.

\bibitem[Sto76]{sto:j:poly}
L.~Stockmeyer.
\newblock The polynomial-time hierarchy.
\newblock {\em Theoretical Computer Science}, 3(1):1--22, 1976.

\bibitem[Tan01]{tan:tPartiallyOutByTheMoreGeneralNicTanCocoonButThatIsSoMuchMo%
reGeneralMostMightNotEvenNoticeTheRelationBetweenTheTwo:tournament-reachabilit%
y}
T.~Tantau.
\newblock A note on the complexity of the reachability problem for tournaments.
\newblock Technical Report TR01-092, Electronic Colloquium on Computational
  Complexity, \mbox{http://www.eccc.uni-trier.de/eccc/}, November 2001.

\bibitem[Wag84]{wag:c:regularities}
K.~Wagner.
\newblock The complexity of problems concerning graphs with regularities.
\newblock In {\em Proceedings of the 11th Symposium on Mathematical Foundations
  of Computer Science}, pages 544--552. Springer-Verlag {\it Lecture Notes in
  Computer Science \#176}, September 1984.

\bibitem[Wag86]{wag:j:succinct}
K.~Wagner.
\newblock The complexity of combinatorial problems with succinct input
  representations.
\newblock {\em Acta Informatica}, 23(3):325--356, 1986.

\bibitem[Wes96]{wes:b:graph}
D.~West.
\newblock {\em Introduction to Graph Theory}.
\newblock Prentice-Hall, 1996.

\bibitem[Wra76]{wra:j:complete}
C.~Wrathall.
\newblock Complete sets and the polynomial-time hierarchy.
\newblock {\em Theoretical Computer Science}, 3(1):23--33, 1976.

\end{thebibliography}
