## 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 |