Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Robust Simulations and Significant Separations

  • Conference paper
Automata, Languages and Programming (ICALP 2011)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 6755))

Included in the following conference series:

Abstract

We define and study a new notion of “robust simulations” between complexity classes which is intermediate between the traditional notions of infinitely-often and almost-everywhere, as well as a corresponding notion of “significant separations”. A language L has a robust simulation in a complexity class C if there is a language in C which agrees with L on arbitrarily large polynomial stretches of input lengths. There is a significant separation of L from C if there is no robust simulation of L ∈ C.

The new notion of simulation is a cleaner and more natural notion of simulation than the infinitely-often notion. We show that various implications in complexity theory such as the collapse of PH if NP = P and the Karp-Lipton theorem have analogues for robust simulations. We then use these results to prove that most known separations in complexity theory, such as hierarchy theorems, fixed polynomial circuit lower bounds, time-space tradeoffs, and the recent theorem of Williams, can be strengthened to significant separations, though in each case, an almost everywhere separation is unknown.

Proving our results requires several new ideas, including a completely different proof of the hierarchy theorem for non-deterministic polynomial time than the ones previously known.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 84.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 109.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Barak, B.: A probabilistic-time hierarchy theorem for “Slightly Non-uniform” algorithms. In: Rolim, J.D.P., Vadhan, S.P. (eds.) RANDOM 2002. LNCS, vol. 2483, pp. 194–208. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  2. Babai, L., Fortnow, L., Lund, C.: Non-deterministic exponential time has two-prover interactive protocols. Computational Complexity 1, 3–40 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  3. Buhrman, H., Fortnow, L., Santhanam, R.: Unconditional lower bounds against advice. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009. LNCS, vol. 5555, pp. 195–209. Springer, Heidelberg (2009)

    Chapter  Google Scholar 

  4. Buhrman, H., Fortnow, L., Thierauf, T.: Nonrelativizing separations. In: Proceedings of 13th Annual IEEE Conference on Computational Complexity, pp. 8–12 (1998)

    Google Scholar 

  5. Cai, J.-Y.: S2 P ⊆ ZPPNP. In: Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, pp. 620–629 (2001)

    Google Scholar 

  6. Cook, S.: A hierarchy for nondeterministic time complexity. In: Fourth Annual ACM Symposium on Theory of Computing, Conference Record, Denver, Colorado, May 1-3, pp. 187–192 (1972)

    Google Scholar 

  7. Cook, S.: Short propositional formulas represent nondeterministic computations. Informations Processing Letters 26(5), 269–270 (1988)

    Article  MathSciNet  MATH  Google Scholar 

  8. Downey, R., Fortnow, L.: Uniformly hard languages. Theoretical Computer Science 298(2), 303–315 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  9. Fortnow, L., Lipton, R., van Melkebeek, D., Viglas, A.: Time-space lower bounds for satisfiability. Journal of the ACM 52(6), 833–865 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  10. Fortnow, L.: Time-space tradeoffs for satisfiability. Journal of Computer and System Sciences 60(2), 337–353 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  11. Fortnow, L., Santhanam, R.: Hierarchy theorems for probabilistic polynomial time. In: Proceedings of the 45th IEEE Symposium on Foundations of Computer Science, pp. 316–324 (2004)

    Google Scholar 

  12. Håstad, J.: Almost optimal lower bounds for small depth circuits. In: Proceedings of the 18th Annual ACM Symposium on Theory of Computing, pp. 6–20 (1986)

    Google Scholar 

  13. Impagliazzo, R., Kabanets, V., Wigderson, A.: In search of an easy witness: Exponential time vs. probabilistic polynomial time. Journal of Computer and System Sciences 65(4), 672–694 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  14. Impagliazzo, R., Wigderson, A.: P = BPP if E requires exponential circuits: Derandomizing the XOR lemma. In: Proceedings of the 29th Annual ACM Symposium on the Theory of Computing, pp. 220–229 (1997)

    Google Scholar 

  15. Kabanets, V.: Easiness assumptions and hardness tests: Trading time for zero error. Journal of Computer and System Sciences 63(2), 236–252 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  16. Kannan, R.: Circuit-size lower bounds and non-reducibility to sparse sets. Information and Control 55(1), 40–56 (1982)

    Article  MathSciNet  MATH  Google Scholar 

  17. Karp, R., Lipton, R.: Turing machines that take advice. L’Enseignement Mathématique 28(2), 191–209 (1982)

    MathSciNet  MATH  Google Scholar 

  18. Klivans, A., van Melkebeek, D.: Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses. In: Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, pp. 659–667 (1999)

    Google Scholar 

  19. Nisan, N., Wigderson, A.: Hardness vs randomness. Journal of Computer and System Sciences 49(2), 149–167 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  20. Razborov, A.: Lower bounds for the monotone complexity of some boolean functions. Soviet Mathematics Doklady 31, 354–357 (1985)

    MATH  Google Scholar 

  21. Razborov, A., Rudich, S.: Natural proofs. Journal of Computer and System Sciences 55(1), 24–35 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  22. Santhanam, R.: Circuit lower bounds for Merlin-Arthur classes. In: Proceedings of 39th Annual Symposium on Theory of Computing, pp. 275–283 (2007)

    Google Scholar 

  23. Seiferas, J., Fischer, M., Meyer, A.: Separating nondeterministic time complexity classes. Journal of the ACM 25(1), 146–167 (1978)

    Article  MathSciNet  MATH  Google Scholar 

  24. Vinodchandran, V.: A note on the circuit complexity of PP. Theoretical Computer Science 347(1-2), 415–418 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  25. van Melkebeek, D., Pervyshev, K.: A generic time hierarchy for semantic models with one bit of advice. In: Proceedings of 21st Annual IEEE Conference on Computational Complexity, pp. 129–144 (2006)

    Google Scholar 

  26. Williams, R.: Improving exhaustive search implies superpolynomial lower bounds. In: Proceedings of the 42nd Annual ACM Symposium on Theory of Computing, pp. 231–240 (2010)

    Google Scholar 

  27. Williams, R.: Non-uniform ACC circuit lower bounds (2010) (manuscript)

    Google Scholar 

  28. Žák, S.: A Turing machine time hierarchy. Theoretical Computer Science 26(3), 327–333 (1983)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Northwestern University, USA

    Lance Fortnow

  2. University of Edinburgh, Scotland, UK

    Rahul Santhanam

Authors
  1. Lance Fortnow
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Rahul Santhanam
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. ICE-TCS, School of Computer Science, Reykjavik University, Menntavegur 1, IS 101, Reykjavik, Iceland

    Luca Aceto

  2. Fakultät für Informatik, Universität Wien, Universitätsstraße10/9, 1090, Wien, Österreich, Austria

    Monika Henzinger

  3. Department of Applied Mathematics, Charles University, Malostranské nám. 25, 118 00, Praha 1, Czech Republic

    Jiří Sgall

Rights and permissions

Reprints and permissions

Copyright information

© 2011 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Fortnow, L., Santhanam, R. (2011). Robust Simulations and Significant Separations. In: Aceto, L., Henzinger, M., Sgall, J. (eds) Automata, Languages and Programming. ICALP 2011. Lecture Notes in Computer Science, vol 6755. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-22006-7_48

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-22006-7_48

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-22005-0

  • Online ISBN: 978-3-642-22006-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation