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 |