Autoreducibility, Nonuniform Completeness, and Random Oracle

We study the complexity class NP and the NP-complete sets. The unifying themes in our work are reducibility and randomness, which we combine in three distinct ways.;1. All known NP-complete sets are highly structured with redundancies that make them autoreducible. Whether this is true for every NP-complete set has important implications for the P vs. NP problem.;We study the autoreducibility of NP-complete sets and obtain optimal separations under strong hypotheses for NP. Under largeness hypotheses for NP, we show that adding a single query to an autoreduction with bounded number of queries makes it stronger. We also prove that autoreductions with constant number of queries are strictly weaker than autoreductions where the number of queries is "unbounded''.;2. 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 largeness hypotheses on NP, we show that nonuniform reductions that use a single bit of advice are stronger than uniform reductions. On the other hand, we prove that if the length of advice is logarithmic, then by increasing the number of queries nonuniformity can be eliminated. We also show that this is not true in general. In particular, if the length of the advice is polynomial, nonuniformity cannot be eliminated. As a result, we separate nonuniform reductions with logarithmic advice from nonuniform reductions with polynomial advice.;3. Bennett and Gill proved that P ≠ NP relative to random oracles. In other words, the class of oracles where PA ≠ NPA has measure 1 with respect to classical Lebesgue measure on infinite binary sequences. We show that the class of oracles where PA = NPA is small with respect to p-measure and p-betting-game measure. This can be considered as the first step towards separating different levels of polynomial hierarchy relative to p-random oracles.