## Abstract

Nonuniformity is a central concept in computational complexity with powerful connections to circuit complexity and randomness. Nonuniform reductions have been used to study the isomorphism conjecture for NP and completeness for larger complexity classes. We study the power of nonuniform reductions for NP-completeness, obtaining both separations and upper bounds for nonuniform completeness vs uniform complessness in NP.

Under various hypotheses, we obtain the following separations:

1. There is a set complete for NP under nonuniform many-one reductions, but not under uniform many-one reductions. This is true even with a single bit of nonuniform advice.

2. There is a set complete for NP under nonuniform many-one reductions with polynomialsize advice, but not under uniform Turing reductions. That is, polynomial nonuniformity is stronger than a polynomial number of queries.

3. For any fixed polynomial p(n), there is a set complete for NP under uniform 2-truth-table reductions, but not under nonuniform many-one reductions that use p(n) advice. That is, giving a uniform reduction a second query makes it more powerful than a nonuniform reduction with fixed polynomial advice.

4. There is a set complete for NP under nonuniform many-one reductions with polynomial advice, but not under nonuniform many-one reductions with logarithmic advice. This hierarchy

theorem also holds for other reducibilities, such as truth-table and Turing.

We also consider uniform upper bounds on nonuniform completeness. Hirahara (2015) showed that unconditionally every set that is complete for NP under nonuniform truth-table reductions that use logarithmic advice is also uniformly Turing-complete. We show that under a derandomization hypothesis, the same statement for truth-table reductions and truth-table completeness also holds.

Under various hypotheses, we obtain the following separations:

1. There is a set complete for NP under nonuniform many-one reductions, but not under uniform many-one reductions. This is true even with a single bit of nonuniform advice.

2. There is a set complete for NP under nonuniform many-one reductions with polynomialsize advice, but not under uniform Turing reductions. That is, polynomial nonuniformity is stronger than a polynomial number of queries.

3. For any fixed polynomial p(n), there is a set complete for NP under uniform 2-truth-table reductions, but not under nonuniform many-one reductions that use p(n) advice. That is, giving a uniform reduction a second query makes it more powerful than a nonuniform reduction with fixed polynomial advice.

4. There is a set complete for NP under nonuniform many-one reductions with polynomial advice, but not under nonuniform many-one reductions with logarithmic advice. This hierarchy

theorem also holds for other reducibilities, such as truth-table and Turing.

We also consider uniform upper bounds on nonuniform completeness. Hirahara (2015) showed that unconditionally every set that is complete for NP under nonuniform truth-table reductions that use logarithmic advice is also uniformly Turing-complete. We show that under a derandomization hypothesis, the same statement for truth-table reductions and truth-table completeness also holds.

Original language | English |
---|---|

Title of host publication | 35th Symposium on Theoretical Aspects of Computer Science |

Subtitle of host publication | (STACS 2018) |

Editors | Rolf Niedermeier, Brigitte Vallée |

Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |

Number of pages | 13 |

Volume | 96 |

ISBN (Print) | 9783959770620 |

DOIs | |

Publication status | Published - 27 Feb 2018 |

Externally published | Yes |

Event | 35th Symposium on Theoretical Aspects of Computer Science - Caen, France Duration: 28 Feb 2018 → 3 Mar 2018 Conference number: 35 |

### Publication series

Name | Leibniz International Proceedings in Informatics |
---|---|

Publisher | Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH |

Volume | 96 |

ISSN (Print) | 1868-8969 |

### Conference

Conference | 35th Symposium on Theoretical Aspects of Computer Science |
---|---|

Abbreviated title | STACS 2018 |

Country/Territory | France |

City | Caen |

Period | 28/02/18 → 3/03/18 |