ECCC-Report TR16-012https://eccc.weizmann.ac.il/report/2016/012Comments and Revisions published for TR16-012en-usMon, 01 Feb 2016 21:00:23 +0200
Paper TR16-012
| Autoreducibility of NP-Complete Sets |
John Hitchcock,
Hadi Shafei
https://eccc.weizmann.ac.il/report/2016/012We 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 or $(k-1)$-T autoreducible.
- For every $k \geq 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$, 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.Mon, 01 Feb 2016 21:00:23 +0200https://eccc.weizmann.ac.il/report/2016/012