Hitchcock, John M. ;
Shafei, Hadi
Nonuniform Reductions and NPCompleteness
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 NP0completeness, 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 manyone reductions, but not under uniform manyone reductions. This is true even with a single bit of nonuniform advice.
2. There is a set complete for NP under nonuniform manyone 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 2truthtable reductions, but not under nonuniform manyone 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 manyone reductions with polynomial ad vice, but not under nonuniform manyone reductions with logarithmic advice. This hierarchy theorem also holds for other reducibilities, such as truthtable 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 truthtable reductions that use logarithmic advice is also uniformly Turingcomplete. We show that under a derandomization hypothesis, the same statement for truthtable reductions and truthtable completeness also holds.
BibTeX  Entry
@InProceedings{hitchcock_et_al:LIPIcs:2018:8521,
author = {John M. Hitchcock and Hadi Shafei},
title = {{Nonuniform Reductions and NPCompleteness}},
booktitle = {35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
pages = {40:140:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770620},
ISSN = {18688969},
year = {2018},
volume = {96},
editor = {Rolf Niedermeier and Brigitte Vall{\'e}e},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8521},
URN = {urn:nbn:de:0030drops85217},
doi = {10.4230/LIPIcs.STACS.2018.40},
annote = {Keywords: computational complexity, NPcompleteness, reducibility, nonuniform complexity}
}
27.02.2018
Keywords: 

computational complexity, NPcompleteness, reducibility, nonuniform complexity 
Seminar: 

35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)

Issue date: 

2018 
Date of publication: 

27.02.2018 