Murray, Cody D. ;
Williams, R. Ryan
Easiness Amplification and Uniform Circuit Lower Bounds
Abstract
We present new consequences of the assumption that timebounded algorithms can be "compressed" with nonuniform circuits. Our main contribution is an "easiness amplification" lemma for circuits. One instantiation of the lemma says: if n^{1+e}time, tilde{O}(n)space computations have n^{1+o(1)} size (nonuniform) circuits for some e > 0, then every problem solvable in polynomial time and tilde{O}(n) space has n^{1+o(1)} size (nonuniform) circuits as well. This amplification has several consequences:
* An easy problem without small LOGSPACEuniform circuits. For all e > 0, we give a natural decision problem, General Circuit n^eComposition, that is solvable in about n^{1+e} time, but we prove that polynomialtime and logarithmicspace preprocessing cannot produce n^{1+o(1)}size circuits for the problem. This shows that there are problems solvable in n^{1+e} time which are not in LOGSPACEuniform n^{1+o(1)} size, the first result of its kind. We show that our lower bound is nonrelativizing, by exhibiting an oracle relative to which the result is false.
* Problems without lowdepth LOGSPACEuniform circuits. For all e > 0, 1 < d < 2, and e < d we give another natural circuit composition problem computable in tilde{O}(n^{1+e}) time, or in O((log n)^d) space (though not necessarily simultaneously) that we prove does not have SPACE[(log n)^e]uniform circuits of tilde{O}(n) size and O((log n)^e) depth. We also show SAT does not have circuits of tilde{O}(n) size and log^{2o(1)}(n) depth that can be constructed in log^{2o(1)}(n) space.
* A strong circuit complexity amplification. For every e > 0, we give a natural circuit composition problem and show that if it has tilde{O}(n)size circuits (uniform or not), then every problem solvable in 2^{O(n)} time and 2^{O(sqrt{n log n})} space (simultaneously) has 2^{O(sqrt{n log n})}size circuits (uniform or not). We also show the same consequence holds assuming SAT has tilde{O}(n)size circuits. As a corollary, if n^{1.1} time computations (or O(n) nondeterministic time computations) have tilde{O}(n)size circuits, then all problems in exponential time and subexponential space (such as quantified Boolean formulas) have significantly subexponentialsize circuits. This is a new connection between the relative circuit complexities of easy and hard problems.
BibTeX  Entry
@InProceedings{murray_et_al:LIPIcs:2017:7542,
author = {Cody D. Murray and R. Ryan Williams},
title = {{Easiness Amplification and Uniform Circuit Lower Bounds}},
booktitle = {32nd Computational Complexity Conference (CCC 2017)},
pages = {8:18:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770408},
ISSN = {18688969},
year = {2017},
volume = {79},
editor = {Ryan O'Donnell},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7542},
URN = {urn:nbn:de:0030drops75421},
doi = {10.4230/LIPIcs.CCC.2017.8},
annote = {Keywords: uniform circuit complexity, time complexity, space complexity, nonrelativizing, amplification}
}
01.08.2017
Keywords: 

uniform circuit complexity, time complexity, space complexity, nonrelativizing, amplification 
Seminar: 

32nd Computational Complexity Conference (CCC 2017)

Issue date: 

2017 
Date of publication: 

01.08.2017 