Autoreducibility of NP-Complete Sets under Strong Hypotheses

作者：Hitchcock John M^*; Shafei Hadi

来源：Computational Complexity, 2018, 27(1): 63-97.

DOI：10.1007/s00037-017-0157-z

• NP-completeness
• autoreducibility
• genericity

We study the polynomial-time autoreducibility of NP-complete sets and obtain separations understrong hypotheses for NP. Assuming there is a p-generic set in NP, we show the following: For every , 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 , 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.
For every , 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-ttautoreducibility.

• 出版日期2018-3