  Nonuniformity is a central concept in computational complexity with powerful
connections to circuit complexity and randomness. Nonuniform reductions have
been used to study the isomorphism conjecture for NP and completeness for
larger complexity classes. We study the power of nonuniform reductions for
NP-completeness, obtaining both separations and upper bounds for nonuniform
completeness vs uniform completeness in NP.
  Under various hypotheses, we obtain the following separations:
  1. There is a set complete for NP under nonuniform many-one reductions, but
not under uniform many-one reductions. This is true even with a single bit of
nonuniform advice.
  2. There is a set complete for NP under nonuniform many-one reductions with
polynomial-size advice, but not under uniform Turing reductions. That is,
polynomial nonuniformity is stronger than a polynomial number of queries.
  3. For any fixed polynomial p(n), there is a set complete for NP under
uniform 2-truth-table reductions, but not under nonuniform many-one reductions
that use p(n) advice. That is, giving a uniform reduction a second query makes
it more powerful than a nonuniform reduction with fixed polynomial advice.
  4. There is a set complete for NP under nonuniform many-one reductions with
polynomial advice, but not under nonuniform many-one reductions with
logarithmic advice. This hierarchy theorem also holds for other reducibilities,
such as truth-table and Turing.
  We also consider uniform upper bounds on nonuniform completeness. Hirahara
(2015) showed that unconditionally every set that is complete for NP under
nonuniform truth-table reductions that use logarithmic advice is also uniformly
Turing-complete. We show that under a derandomization hypothesis, the same
statement for truth-table reductions and truth-table completeness also holds.
