Go to the corresponding LIPIcs Volume Portal |
Murray, Cody D. ;
Williams, R. Ryan
Easiness Amplification and Uniform Circuit Lower Bounds
pdf-format:
LIPIcs-CCC-2017-8.pdf (0.6 MB)
Abstract
We present new consequences of the assumption that time-bounded algorithms can be "compressed" with non-uniform 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 (non-uniform) circuits for some e > 0, then every problem solvable in polynomial time and tilde{O}(n) space has n^{1+o(1)} size (non-uniform) circuits as well. This amplification has several consequences:
* An easy problem without small LOGSPACE-uniform circuits. For all e > 0, we give a natural decision problem, General Circuit n^e-Composition, that is solvable in about n^{1+e} time, but we prove that polynomial-time and logarithmic-space 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 LOGSPACE-uniform n^{1+o(1)} size, the first result of its kind. We show that our lower bound is non-relativizing, by exhibiting an oracle relative to which the result is false.
* Problems without low-depth LOGSPACE-uniform 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^{2-o(1)}(n) depth that can be constructed in log^{2-o(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 subexponential-size 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:1--8:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-040-8},
ISSN = {1868-8969},
year = {2017},
volume = {79},
editor = {Ryan O'Donnell},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7542},
URN = {urn:nbn:de:0030-drops-75421},
doi = {10.4230/LIPIcs.CCC.2017.8},
annote = {Keywords: uniform circuit complexity, time complexity, space complexity, non-relativizing, amplification}
}
Keywords:
uniform circuit complexity, time complexity, space complexity, non-relativizing, amplification
Collection:
32nd Computational Complexity Conference (CCC 2017)
Issue Date:
2017
Date of publication:
01.08.2017