Bennett and Gill (1981) showed that P^A != NP^A != coNP^A for a random
oracle A, with probability 1. We investigate whether this result
extends to individual polynomial-time random oracles. We consider two
notions of random oracles: p-random oracles in the sense of
martingales and resource-bounded measure (Lutz, 1992; Ambos-Spies ... more >>>

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 ... more >>>

We study the polynomial-time autoreducibility of NP-complete sets and obtain separations under strong hypotheses for NP. Assuming there is a p-generic set in NP, we show the following:

- For every $k \geq 2$, there is a $k$-T-complete set for NP that is $k$-T autoreducible, but is not $k$-tt autoreducible ... more >>>