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-Tautoreducibility from 2-tt-autoreducibility.
- 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-Tautoreducibility from 2-tt-autoreducibility.
| Original language | English |
|---|---|
| Title of host publication | 33rd Symposium on Theoretical Aspects of Computer Science |
| Subtitle of host publication | STACS 2016 |
| Editors | Nicolas Ollinger, Heribert Vollmer |
| Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
| Number of pages | 12 |
| Volume | 47 |
| ISBN (Print) | 9783959770019 |
| DOIs | |
| Publication status | Published - 16 Feb 2016 |
| Externally published | Yes |
| Event | 33rd Symposium on Theoretical Aspects of Computer Science - Orléans, France Duration: 17 Feb 2016 → 20 Feb 2016 Conference number: 33 |
Publication series
| Name | Leibniz International Proceedings in Informatics |
|---|---|
| Publisher | Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH |
| Volume | 47 |
| ISSN (Print) | 1868-8969 |
Conference
| Conference | 33rd Symposium on Theoretical Aspects of Computer Science |
|---|---|
| Abbreviated title | STACS 2016 |
| Country/Territory | France |
| City | Orléans |
| Period | 17/02/16 → 20/02/16 |