Document Open Access Logo

Easiness Amplification and Uniform Circuit Lower Bounds

Authors Cody D. Murray, R. Ryan Williams

PDF

File

Thumbnail PDF
PDF
LIPIcs.CCC.2017.8.pdf
  • Filesize: 0.57 MB
  • 21 pages

Document Identifiers

Subject Classification

Keywords
  • uniform circuit complexity
  • time complexity
  • space complexity
  • non-relativizing
  • amplification

Metrics

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.

Cite As Get BibTex

Cody D. Murray and R. Ryan Williams. Easiness Amplification and Uniform Circuit Lower Bounds. In 32nd Computational Complexity Conference (CCC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 79, pp. 8:1-8:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.CCC.2017.8

Author Details

Cody D. Murray
R. Ryan Williams

References

  1. Miklos Ajtai. Determinism versus non-determinism for linear time RAMs (extended abstract). In STOC: ACM Symposium on Theory of Computing (STOC), 1999. Google Scholar
  2. Eric Allender and Michal Koucký. Amplifying lower bounds by means of self-reducibility. J. ACM, 57(3):14:1-14:36, 2010. Google Scholar
  3. Eric Allender, Michal Koucký, Detlef Ronneburger, Sambuddha Roy, and V. Vinay. Time-space tradeoffs in the counting hierarchy. In Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001, pages 295-302, 2001. Google Scholar
  4. Sanjeev Arora and Boaz Barak. Complexity Theory: A Modern Approach. Cambridge University Press, Cambridge, 2009. Google Scholar
  5. Paul Beame, Michael E. Saks, Xiaodong Sun, and Erik Vee. Time-space trade-off lower bounds for randomized computation of decision problems. J. ACM, 50(2):154-195, 2003. Google Scholar
  6. Samuel R. Buss and Ryan Williams. Limits on alternation trading proofs for time-space lower bounds. Computational Complexity, 24(3):533-600, 2015. Google Scholar
  7. Stephen A. Cook. Deterministic CFL’s are accepted simultaneously in polynomial time and log squared space. In STOC, pages 338-345, 1979. Google Scholar
  8. Ning Ding. Some new consequences of the hypothesis that P has fixed polynomial-size circuits. In Theory and Applications of Models of Computation TAMC, pages 75-86, 2015. Google Scholar
  9. Magnus Gausdal Find, Alexander Golovnev, Edward A. Hirsch, and Alexander S. Kulikov. A better-than-3n lower bound for the circuit complexity of an explicit function. Electronic Colloquium on Computational Complexity (ECCC), 22:166, 2015. URL: http://eccc.hpi-web.de/report/2015/166.
  10. Lance Fortnow. Time-space tradeoffs for satisfiability. Journal of Computer and System Sciences, 60(2):337-353, April 2000. Google Scholar
  11. Lance Fortnow, Richard Lipton, Dieter van Melkebeek, and Anastasios Viglas. Time-space lower bounds for satisfiability. J. ACM, 52(6):833-865, 2005. Google Scholar
  12. Lance Fortnow, Rahul Santhanam, and Ryan Williams. Fixed polynomial size circuit bounds. In Proceedings of 24th Annual IEEE Conference on Computational Complexity, pages 19-26, 2009. Google Scholar
  13. Juris Hartmanis and Richard Stearns. On the computational complexity of algorithms. Trans. Amer. Math. Soc. (AMS), 117:285-306, 1965. Google Scholar
  14. Frederick Hennie and Richard Stearns. Two-tape simulation of multitape Turing machines. Journal of the ACM, 13(4):533-546, October 1966. Google Scholar
  15. John Hopcroft, Wolfgang Paul, and Leslie Valiant. On time versus space. Journal of the ACM, 24(2):332-337, April 1977. Google Scholar
  16. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 62(4):512-530, 2001. Google Scholar
  17. Richard Lipton. Some consequences of our failure to prove non-linear lower bounds on explicit functions. In Proceedings of 9th Annual Structure in Complexity Theory Conference, pages 79-87, 1994. Google Scholar
  18. Richard J. Lipton and Anastasios Viglas. Non-uniform depth of polynomial time and space simulations. In Proceedings of Fundamentals of Computation Theory, 14th International Symposium (FCT), pages 311-320, 2003. Google Scholar
  19. Richard J. Lipton and Ryan Williams. Amplifying circuit lower bounds against polynomial time, with applications. Computational Complexity, 22(2):311-343, 2013. Google Scholar
  20. V. Nepomnjascii. Rudimentary predicates and turing calculations. Soviet Mathematics - Doklady, 11(6):1462-1465, 1970. Google Scholar
  21. Nicholas Pippenger. On simultaneous resource bounds (preliminary version). In FOCS, pages 307-311, 1979. Google Scholar
  22. Nicholas Pippenger and Michael J. Fischer. Relations among complexity measures. J. ACM, 26(2):361-381, 1979. Google Scholar
  23. Rüdiger Reischuk. Einführung in die Komplexitätstheorie. Teubner, 1990. Google Scholar
  24. Walter L. Ruzzo, Janos Simon, and Martin Tompa. Space-bounded hierarchies and probabilistic computations. J. Comput. Syst. Sci., 28(2):216-230, 1984. Google Scholar
  25. Rahul Santhanam and Ryan Williams. On uniformity and circuit lower bounds. Computational Complexity, 23(2):177-205, 2014. Preliminary version in CCC'13. Google Scholar
  26. Richard Stearns, Juris Hartmanis, and Philip Lewis. Hierarchies of memory limited computations. In Proceedings of the Sixth Annual Symposium on Switching Circuit Theory and Logical Design, pages 179-190. IEEE, 1965. Google Scholar
  27. Richard Stearns, Juris Hartmanis, and Philip Lewis. Hierarchies of memory limited computations. In Proceedings of the Sixth Annual Symposium on Switching Circuit Theory and Logical Design, pages 179-190. IEEE, 1965. Google Scholar
  28. Dieter Van Melkebeek. A survey of lower bounds for satisfiability and related problems, volume 7. Now Publishers Inc, 2007. Google Scholar
  29. Heribert Vollmer. Introduction to circuit complexity: a uniform approach. Springer Science &Business Media, 1999. Google Scholar
  30. R. Ryan Williams. Time-space tradeoffs for counting NP solutions modulo integers. Computational Complexity, 17(2):179-219, 2008. Google Scholar
  31. Ryan Williams. Alternation-trading proofs, linear programming, and lower bounds. TOCT, 5(2):6, 2013. Google Scholar
  32. Christopher Wilson. Relativized circuit complexity. Journal of Computer and System Sciences, 31(2):169-181, 1985. Google Scholar
  33. Stanislav Žák. A Turing machine time hierarchy. Theoretical Computer Science, 26(3):327-333, October 1983. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact