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:
For every 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 ≥ 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 ∩ coNP, we show:
For every 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.
Autoreducibility of NP-Complete Sets, Proceedings of the
33rd International Symposium on Theoretical Aspects of Computer
Science (Orléans, France, February 17-20, 2016).
[DOI | pdf]
Autoreducibility of NP-Complete Sets, Technical Report TR16-012,
Electronic Colloquium on Computational Complexity, 2016.
[pdf]