Autoreducibility of NP-Complete Sets under Strong Hypotheses

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}$$kź2, there is a k-T-complete set for NP that is k-T-autoreducible, but is not k-tt-autoreducible or (k ź 1)-T-autoreducible.źFor every $${k \geq 3}$$kź3, there is a k-tt-complete set for NP that is k-tt-autoreducible, but is not (k ź 1)-tt-autoreducible or (k ź 2)-T-autoreducible.źThere is a tt-complete set for NP that is tt-autoreducible, but is not btt-autoreducible. Under the stronger assumption that there is a p-generic set in NP $${\cap}$$ź coNP, we show: źFor every $${k \geq 2}$$kź2, there is a k-tt-complete set for NP that is k-tt-autoreducible, but is not (k ź 1)-T-autoreducible. 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.