  There is no single canonical polynomial-time version of the Axiom of Choice
(AC); several statements of AC that are equivalent in Zermelo-Fraenkel (ZF) set
theory are already inequivalent from a constructive point of view, and are
similarly inequivalent from a complexity-theoretic point of view. In this paper
we show that many classical formulations of AC, when restricted to polynomial
time in natural ways, are equivalent to standard complexity-theoretic
hypotheses, including several that were of interest to Selman. This provides a
unified view of these hypotheses, and we hope provides additional motivation
for studying some of the lesser-known hypotheses that appear here.
  Additionally, because several classical forms of AC are formulated in terms
of cardinals, we develop a theory of polynomial-time cardinality. Nerode &
Remmel (Contemp. Math. 106, 1990 and Springer Lec. Notes Math. 1432, 1990)
developed a related theory, but restricted to unary sets. Downey (Math. Reviews
MR1071525) suggested that such a theory over larger alphabets could have
interesting connections to more standard complexity questions, and we
illustrate some of those connections here.
  The connections between AC, cardinality, and complexity questions also allow
us to highlight some of Selman's work. We hope this paper is more of a
beginning than an end, introducing new concepts and raising many new questions,
ripe for further research.
