Autoreducibility of NP-Complete Sets under Strong Hypotheses

John M. Hitchcock and Hadi Shafei

Abstract:
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:

Under the stronger assumption that there is a p-generic set in NP ∩ coNP, we show: Our proofs are based on constructions from separating NP-completeness notions. For example, the construction of a 2-T-complete set for NP that is not 2-tt-complete also separates 2-T-autoreducibility from 2-tt-autoreducibility.

Journal version:

Preliminary versions: