Document Open Access Logo

Superlinear Lower Bounds Based on ETH

Authors András Z. Salamon , Michael Wehar

PDF
Thumbnail PDF

File

LIPIcs.STACS.2022.55.pdf
  • Filesize: 0.71 MB
  • 16 pages

Document Identifiers

Author Details

András Z. Salamon
  • School of Computer Science, University of St Andrews, UK
Michael Wehar
  • Computer Science Department, Swarthmore College, PA, USA

Funding

  • Salamon, András Z.: EPSRC grants EP/P015638/1 and EP/V027182/1.

Acknowledgements

We greatly appreciate the help and suggestions that we received. We are especially grateful to Kenneth Regan and Jonathan Buss who shared a manuscript [Buss and Regan, 2014] on speed-up results relating time and space. We also thank Michael Fischer, Mike Paterson, and Nick Pippenger, who tracked down two manuscripts related to circuit simulations. In addition, we thank Karl Bringmann whose advice helped us to better align this work with recent advances in fine-grained complexity. Likewise, we recognize helpful discussions with Henning Fernau and all of the participants at the workshop on Modern Aspects of Complexity Within Formal Languages (sponsored by DFG). Finally, we very much appreciate all of the feedback from Joseph Swernofsky, suggestions from Ryan Williams, and comments from anonymous referees.

Cite AsGet BibTex

András Z. Salamon and Michael Wehar. Superlinear Lower Bounds Based on ETH. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 55:1-55:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.STACS.2022.55

Abstract

We introduce techniques for proving superlinear conditional lower bounds for polynomial time problems. In particular, we show that CircuitSAT for circuits with m gates and log(m) inputs (denoted by log-CircuitSAT) is not decidable in essentially-linear time unless the exponential time hypothesis (ETH) is false and k-Clique is decidable in essentially-linear time in terms of the graph’s size for all fixed k. Such conditional lower bounds have previously only been demonstrated relative to the strong exponential time hypothesis (SETH). Our results therefore offer significant progress towards proving unconditional superlinear time complexity lower bounds for natural problems in polynomial time.

Subject Classification

ACM Subject Classification
  • Theory of computation → Models of computation
  • Theory of computation → Complexity classes
Keywords
  • Circuit Satisfiability
  • Conditional Lower Bounds
  • Exponential Time Hypothesis
  • Limited Nondeterminism

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Amir Abboud, Thomas Dueholm Hansen, Virginia Vassilevska Williams, and Ryan Williams. Simulating branching programs with edit distance and friends: Or: a polylog shaved is a lower bound made. In Proceedings of the 48th Annual ACM Symposium on Theory of Computing, STOC 2016, pages 375-388. Association for Computing Machinery, 2016. URL: https://doi.org/10.1145/2897518.2897653.
  2. Karl A. Abrahamson, Rodney G. Downey, and Michael R. Fellows. Fixed-parameter tractability and completeness IV: On completeness for W[P] and PSPACE analogues. Annals of Pure and Applied Logic, 73(3):235-276, 1995. URL: https://doi.org/10.1016/0168-0072(94)00034-Z.
  3. Akeo Adachi, Shigeki Iwata, and Takumi Kasai. Some combinatorial game problems require Ω(n^k) time. J. ACM, 31(2):361-376, March 1984. URL: https://doi.org/10.1145/62.322433.
  4. Carme Àlvarez, Josep Díaz, and Jacobo Torán. Complexity classes with complete problems between P and NP-C. In J. Csirik, J. Demetrovics, and F. Gécseg, editors, FCT 1989: Proceedings of the 7th International Conference on Fundamentals of Computation Theory, volume 380 of LNCS, pages 13-24. Springer, 1989. URL: https://doi.org/10.1007/3-540-51498-8_2.
  5. R. Beigel and J. Goldsmith. Downward separation fails catastrophically for limited nondeterminism classes. SIAM Journal on Computing, 27(5):1420-1429, 1998. URL: https://doi.org/10.1137/S0097539794277421.
  6. Eli Ben-Sasson and Emanuele Viola. Short PCPs with projection queries. In Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias, editors, ICALP 2014: International Colloquium on Automata, Languages, and Programming, volume 8572 of LNCS, pages 163-173. Springer, 2014. URL: https://doi.org/10.1007/978-3-662-43948-7_14.
  7. Karl Bringmann. Fine-grained complexity theory (tutorial). In Rolf Niedermeier and Christophe Paul, editors, STACS 2019: 36th International Symposium on Theoretical Aspects of Computer Science, volume 126 of LIPIcs, pages 4:1-4:7. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.STACS.2019.4.
  8. Jonathan Buss and Judy Goldsmith. Nondeterminism within P. SIAM J. Comput., 22(3):560-572, 1993. URL: https://doi.org/10.1137/0222038.
  9. Jonathan Buss and Kenneth Regan. Simultaneous bounds on time and space. Manuscript, 2014. Google Scholar
  10. Liming Cai and Jianer Chen. On the amount of nondeterminism and the power of verifying. SIAM J. Comput., 26(3):733-750, 1997. URL: https://doi.org/10.1137/S0097539793258295.
  11. Chris Calabro, Russell Impagliazzo, and Ramamohan Paturi. The complexity of satisfiability of small depth circuits. In Jianer Chen and Fedor V. Fomin, editors, IWPEC 2009: Parameterized and Exact Computation, volume 5917 of LNCS, pages 75-85. Springer, 2009. URL: https://doi.org/10.1007/978-3-642-11269-0_6.
  12. Lijie Chen, Ce Jin, and R. Ryan Williams. Sharp threshold results for computational complexity. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, pages 1335-1348. Association for Computing Machinery, 2020. URL: https://doi.org/10.1145/3357713.3384283.
  13. Stephen A. Cook. The complexity of theorem-proving procedures. In Proceedings of the Third Annual ACM Symposium on Theory of Computing, STOC 1971, pages 151-158. Association for Computing Machinery, 1971. URL: https://doi.org/10.1145/800157.805047.
  14. Stephen A. Cook. Short propositional formulas represent nondeterministic computations. Information Processing Letters, 26(5):269-270, 1988. URL: https://doi.org/10.1016/0020-0190(88)90152-4.
  15. Stephen A. Cook and Robert A. Reckhow. Time bounded random access machines. Journal of Computer and System Sciences, 7(4):354-375, 1973. URL: https://doi.org/10.1016/S0022-0000(73)80029-7.
  16. Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-21275-3.
  17. J. Díaz and J. Torán. Classes of bounded nondeterminism. Mathematical Systems Theory, 23(1):21-32, 1990. URL: https://doi.org/10.1007/BF02090764.
  18. Graham E. Farr. Topics in computational complexity. PhD thesis, University of Oxford, 1986. URL: https://ora.ox.ac.uk/objects/uuid:ad3ed1a4-fea4-4b46-8e7a-a0c6a3451325/.
  19. Uriel Feige and Joe Kilian. On Limited versus Polynomial Nondeterminism. Chicago Journal of Theoretical Computer Science, 1997(1), March 1997. URL: http://cjtcs.cs.uchicago.edu/articles/1997/1/cj97-01.pdf.
  20. Lance Fortnow and Rahul Santhanam. New Non-Uniform Lower Bounds for Uniform Classes. In Ran Raz, editor, CCC 2016: 31st Conference on Computational Complexity, volume 50 of Leibniz International Proceedings in Informatics (LIPIcs), pages 19:1-19:14. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.CCC.2016.19.
  21. Judy Goldsmith, Matthew A. Levy, and Martin Mundhenk. Limited nondeterminism. SIGACT News, 27(2):20-29, 1996. URL: https://doi.org/10.1145/235767.235769.
  22. Yuri Gurevich and Saharon Shelah. Nearly linear time. In Albert R. Meyer and Michael A. Taitslin, editors, Logic at Botik 1989, volume 363 of LNCS, pages 108-118. Springer, 1989. URL: https://doi.org/10.1007/3-540-51237-3_10.
  23. J. Hartmanis and R. E. Stearns. On the computational complexity of algorithms. Transactions of the AMS, 117:285-306, 1965. URL: https://doi.org/10.1090/S0002-9947-1965-0170805-7.
  24. F.C. Hennie. One-tape, off-line Turing machine computations. Information and Control, 8(6):553-578, 1965. URL: https://doi.org/10.1016/S0019-9958(65)90399-2.
  25. Steven Homer and Alan L. Selman. Computability and Complexity Theory. Springer, 2nd edition, 2011. Google Scholar
  26. Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-SAT. Journal of Computer and System Sciences, 62(2):367-375, 2001. URL: https://doi.org/10.1006/jcss.2000.1727.
  27. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 63(4):512-530, 2001. URL: https://doi.org/10.1006/jcss.2001.1774.
  28. Richard J. Lipton and Ryan Williams. Amplifying circuit lower bounds against polynomial time with applications. In Proceedings of the Annual IEEE Conference on Computational Complexity, CCC 2012, pages 1-9, 2012. URL: https://doi.org/10.1109/CCC.2012.44.
  29. Chandra M. R. Kintala and Patrick C. Fischer. Computations with a restricted number of nondeterministic steps (extended abstract). In Proceedings of the ninth annual ACM symposium on Theory of computing, STOC 1977, pages 178-185. Association for Computing Machinery, 1977. URL: https://doi.org/10.1145/800105.803407.
  30. Chandra M. R. Kintala and Patrick C. Fischer. Refining nondeterminism in relativized polynomial-time bounded computations. SIAM J. Comput., 9(1):46-53, 1980. URL: https://doi.org/10.1137/0209003.
  31. Kojiro Kobayashi. On proving time constructibility of functions. Theoretical Computer Science, 35:215-225, 1985. URL: https://doi.org/10.1016/0304-3975(85)90015-5.
  32. Leonid Anatolevich Levin. Universal sequential search problems. Problemy peredachi informatsii, 9(3):115-116, 1973. Google Scholar
  33. Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Lower bounds based on the exponential time hypothesis. Bulletin of the EATCS, pages 41-71, 2011. Google Scholar
  34. Wolfgang Maass. Quadratic lower bounds for deterministic and nondeterministic one-tape turing machines. In Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing, STOC 1984, pages 401-408. Association for Computing Machinery, 1984. URL: https://doi.org/10.1145/800057.808706.
  35. Xu Mei-rui, John E. Doner, and Ronald V. Book. Refining nondeterminism in relativizations of complexity classes. J. ACM, 30(3):677 - -685, 1983. URL: https://doi.org/10.1145/2402.322399.
  36. Ramamohan Paturi and Pavel Pudlak. On the complexity of circuit satisfiability. In Proceedings of the Forty-second ACM symposium on Theory of computing, STOC 2010, pages 241-250. ACM, 2010. URL: https://doi.org/10.1145/1806689.1806724.
  37. Nicholas Pippenger and Michael J. Fischer. Relations among complexity measures. J. ACM, 26(2):361-381, 1979. URL: https://doi.org/10.1145/322123.322138.
  38. Rahul Santhanam. On separators, segregators and time versus space. In Proceedings of the Sixteenth Annual Conference on Computational Complexity, CCC 2001, pages 286-294, 2001. URL: https://doi.org/10.1109/CCC.2001.933895.
  39. Joseph Swernofsky and Michael Wehar. On the complexity of intersecting regular, context-free, and tree languages. In Magnús M. Halldórsson, Kazuo Iwama, Naoki Kobayashi, and Bettina Speckmann, editors, ICALP 2015: Automata, Languages, and Programming - 42nd International Colloquium, Proceedings, Part II, volume 9135 of LNCS, pages 414-426. Springer, 2015. URL: https://doi.org/10.1007/978-3-662-47666-6_33.
  40. Virginia Vassilevska. Efficient algorithms for clique problems. Information Processing Letters, 109(4):254-257, 2009. URL: https://doi.org/10.1016/j.ipl.2008.10.014.
  41. Michael Wehar. On the Complexity of Intersection Non-Emptiness Problems. PhD thesis, State University of New York at Buffalo, 2016. URL: http://michaelwehar.com/documents/mwehar_dissertation.pdf.
  42. Ryan Williams. A new algorithm for optimal 2-constraint satisfaction and its implications. Theoretical Computer Science, 348(2):357-365, 2005. URL: https://doi.org/10.1016/j.tcs.2005.09.023.
  43. Ryan Williams. Improving exhaustive search implies superpolynomial lower bounds. SIAM J. Comput., 42(3):1218-1244, 2013. URL: https://doi.org/10.1137/10080703X.
  44. Ryan Williams. Non-uniform ACC circuit lower bounds. J. ACM, 61(1):2:1-2:32, 2014. URL: https://doi.org/10.1145/2559903.
  45. Virginia Vassilevska Williams. Hardness of easy problems: Basing hardness on popular conjectures such as the strong exponential time hypothesis (invited talk). In IPEC 2015: Proc. of the 10th International Symposium on Parameterized and Exact Computation, volume 43 of LIPICs, pages 17-29, 2015. URL: https://doi.org/10.4230/LIPIcs.IPEC.2015.17.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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