Document Open Access Logo

New Non-Uniform Lower Bounds for Uniform Classes

Authors Lance Fortnow, Rahul Santhanam

PDF
Thumbnail PDF

File

LIPIcs.CCC.2016.19.pdf
  • Filesize: 0.49 MB
  • 14 pages

Document Identifiers

Author Details

Lance Fortnow
Rahul Santhanam

Cite As Get BibTex

Lance Fortnow and Rahul Santhanam. New Non-Uniform Lower Bounds for Uniform Classes. In 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 50, pp. 19:1-19:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.CCC.2016.19

Abstract

We strengthen the nondeterministic hierarchy theorem for non-deterministic polynomial time to show that the lower bound holds against sub-linear advice. More formally, we show that for any constants d and d' such that 1 <= d < d', and for any time-constructible 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 almost-everywhere hierarchy theorem for non-deterministic classes which use a sub-linear amount of non-determinism, 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 NP-uniform non-deterministic 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 P-uniform circuits of size O(n^k) for any fixed k. As another application, we show strong non-uniform lower bounds for the complexity class RE of languages decidable in randomized linear exponential time with one sided error.

Subject Classification

Keywords
  • Computational complexity
  • nondeterminism
  • nonuniform complexity

Metrics

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

References

  1. Eric Allender, Richard Beigel, Ulrich Hertrampf, and Steven Homer. Almost-everywhere complexity hierarchies for nondeterministic time. Theoretical Computer Science, 115(2):225-241, 19 July 1993. Google Scholar
  2. Eric Allender and Vivek Gore. A uniform circuit lower bound for the permanent. SIAM Journal on Computing, 23(5):1026-1049, 1994. Google Scholar
  3. László Babai, Lance Fortnow, Noam Nisan, and Avi Wigderson. BPP has subexponential time simulations unless EXPTIME has publishable proofs. Computational Complexity, 3(4):307-318, 1993. Google Scholar
  4. D. Bovet, P. Crescenzi, and R. Silvestri. A uniform approach to define complexity classes. Theoretical Computer Science, 104:263-283, 1992. Google Scholar
  5. Harry Buhrman, Lance Fortnow, and Rahul Santhanam. Unconditional lower bounds against advice. In Proc. of 36th Int'l Colloquium on Automata, Languages and Programming, pages 195-209, 2009. Google Scholar
  6. Stephen Cook. A hierarchy for nondeterministic time complexity. In Proc. of the 4th Annual ACM Symp. on Theory of Computing, pages 187-192, Denver, Colorado, 1-3 May 1972. Google Scholar
  7. Lance Fortnow, Richard Lipton, Dieter van Melkebeek, and Anastasios Viglas. Time-space lower bounds for satisfiability. Journal of the ACM, 52(6):833-865, 2005. Google Scholar
  8. Lance Fortnow and Rahul Santhanam. Robust simulations and significant separations. In Proc. of the 38th Int'l Colloquium on Automata, Languages and Programming, pages 569-580, 2011. Google Scholar
  9. Lance Fortnow, Rahul Santhanam, and Luca Trevisan. Promise hierarchies. Electronic Colloquium on Computational Complexity (ECCC), 11(98), 2004. Google Scholar
  10. Lance Fortnow, Rahul Santhanam, and Luca Trevisan. Hierarchies for semantic classes. In Proc. of the 37th Annual ACM Symp. on Theory of Computing, 2005. Google Scholar
  11. Juris Hartmanis and Richard Stearns. On the computational complexity of algorithms. Trans. Amer. Math. Soc. (AMS), 117:285-306, 1965. Google Scholar
  12. Frederick Hennie and Richard Stearns. Two-tape simulation of multitape Turing machines. Journal of the ACM, 13(4):533-546, October 1966. Google Scholar
  13. J. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Language, and Computation. Addison-Wesley, Reading, MA, 1979. Google Scholar
  14. Ravi Kannan. Circuit-size lower bounds and non-reducibility to sparse sets. Information and Control, 55(1):40-56, 1982. Google Scholar
  15. Noam Nisan and Avi Wigderson. Hardness vs randomness. Journal of Computer and System Sciences, 49(2):149-167, 1994. Google Scholar
  16. Rahul Santhanam and Ryan Williams. On medium-uniformity and circuit lower bounds. In Proc. of the 28th Annual IEEE Conf. on Computational Complexity, pages 15-23, 2013. Google Scholar
  17. Joel Seiferas, Michael Fischer, and Albert Meyer. Separating nondeterministic time complexity classes. Journal of the ACM, 25(1):146-167, January 1978. Google Scholar
  18. Richard Stearns, Juris Hartmanis, and Philip Lewis. Hierarchies of memory limited computations. In Proc. of the 6th Annual Symp. on Switching Circuit Theory and Logical Design, pages 179-190. IEEE, 1965. Google Scholar
  19. Ryan Williams. Non-uniform ACC circuit lower bounds. In Proc. of 26th Annual IEEE Conf. on Computational Complexity, pages 115-125, 2011. Google Scholar
  20. Stanislav Žák. A Turing machine time hierarchy. Theoretical Computer Science, 26(3):327-333, October 1983. Google Scholar
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 About DROPS Imprint Privacy Contact