Fortnow, Lance ;
Santhanam, Rahul
New NonUniform Lower Bounds for Uniform Classes
Abstract
We strengthen the nondeterministic hierarchy theorem for nondeterministic polynomial time to show that the lower bound holds against sublinear advice. More formally, we show that for any constants d and d' such that 1 <= d < d', and for any timeconstructible bound t=o(n^d), there is a language in NTIME(n^d) which is not in NTIME(t)/n^{1/d'}. The best known earlier separation of Fortnow, Santhanam and Trevisan could only handle o(log(n)) bits of advice in the lower bound, and was not tight with respect to the time bounds.
We generalize our hierarchy theorem to work for other syntactic complexity measures between polynomial time and polynomial space, including alternating polynomial time with any fixed number of alternations. We also use our technique to derive an almosteverywhere hierarchy theorem for nondeterministic classes which use a sublinear amount of nondeterminism, i.e., the lower bound holds on all but finitely many input lengths rather than just on infinitely many.
As one application of our main result, we derive a new lower bound for NP against NPuniform nondeterministic circuits of size O(n^k) for any fixed k. This result is a significant strengthening of a result of Kannan, which states that not all of NP can be solved with Puniform circuits of size O(n^k) for any fixed k. As another application, we show strong nonuniform lower bounds for the complexity class RE of languages decidable in randomized linear exponential time with one sided error.
BibTeX  Entry
@InProceedings{fortnow_et_al:LIPIcs:2016:5850,
author = {Lance Fortnow and Rahul Santhanam},
title = {{New NonUniform Lower Bounds for Uniform Classes}},
booktitle = {31st Conference on Computational Complexity (CCC 2016)},
pages = {19:119:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770088},
ISSN = {18688969},
year = {2016},
volume = {50},
editor = {Ran Raz},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5850},
URN = {urn:nbn:de:0030drops58503},
doi = {10.4230/LIPIcs.CCC.2016.19},
annote = {Keywords: Computational complexity, nondeterminism, nonuniform complexity}
}
2016
Keywords: 

Computational complexity, nondeterminism, nonuniform complexity 
Seminar: 

31st Conference on Computational Complexity (CCC 2016)

Issue date: 

2016 
Date of publication: 

2016 