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

Dimension and the Structure of Complexity Classes

  • Published:
Theory of Computing Systems Aims and scope Submit manuscript

Abstract

We prove three results on the dimension structure of complexity classes. (1) The Point-to-Set Principle, which has recently been used to prove several new theorems in fractal geometry, has resource-bounded instances. These instances characterize the resource-bounded dimension of a set X of languages in terms of the relativized resource-bounded dimensions of the individual elements of X, provided that the former resource bound is large enough to parametrize the latter. Thus for example, the dimension of a class X of languages in EXP is characterized in terms of the relativized p-dimensions of the individual elements of X. (2) Every language that is \({\leq ^{P}_{m}}\)-reducible to a p-selective set has p-dimension 0, and this fact holds relative to arbitrary oracles. Combined with a resource-bounded instance of the Point-to-Set Principle, this implies that if NP has positive dimension in EXP, then no quasipolynomial time selective language is \({\leq ^{P}_{m}}\)-hard for NP. (3) If the set of all disjoint pairs of NP languages has dimension 1 in the set of all disjoint pairs of EXP languages, then NP has positive dimension in EXP.

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

Access this article

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

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Ambos-Spies, K., Merkle, W., Reimann, J., Stephan, F.: Hausdorff dimension in exponential time. In: Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, June 18–21, 2001, pp 210–217. IEEE Computer Society (2001)

  2. Bishop, C. J., Peres, Y.: Fractals in Probability and Analysis. Cambridge University Press, Cambridge (2017)

  3. Buhrman, H., Longpré, L.: Compressibility and resource bounded measure. In: Proceedings of the Thirteenth Symposium on Theoretical Aspects of Computer Science, pp 13–24. Springer, Berlin (1996)

  4. Dose, T., Glaßer, C.: NP-Completeness, Proof Systems, and Disjoint NP-Pairs. In: C. Paul, M. Bläser (eds.) 37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020, March 10–13, 2020, Montpellier, France, LIPIcs, vol. 154, pp 9:1–9:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)

  5. Even, S., Selman, A. L., Yacobi, Y.: The complexity of promise problems with applications to public-key cryptography. Inf. Control. 61(2), 159–173 (1984)

    Article  MathSciNet  MATH  Google Scholar 

  6. Falconer, K.: Fractal Geometry: Mathematical Foundations and Applications, 3rd edn. Wiley, New York (2014)

    MATH  Google Scholar 

  7. Fortnow, L., Lutz, J. H., Mayordomo, E.: Inseparability and strong hypotheses for disjoint NP pairs. Theory Comput. Syst. 51, 229–247 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  8. Glaßer, C., Selman, A.L., Sengupta, S., Zhang, L.: Disjoint NP-pairs. SIAM J. Comput. 33, 1369–1416 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  9. Glaßer, C., Selman, A.L., Sengupta, S.: Reductions between disjoint NP-pairs. Inf. Comput. 200, 247–267 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  10. Glaßer, C., Selman, A.L., Zhang, L.: Canonical disjoint NP-pairs of propositional proof systems. Theor. Comput. Sci. 370, 60–73 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  11. Glaßer, C., Selman, A.L., Zhang, L.: The informational content of canonical disjoint NP-pairs. Int. J. Found. Comput. Sci. 20(3), 501–522 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  12. Glaßer, C., Hughes, A., Selman, A.L., Wisiol, N.: Disjoint NP-pairs and propositional proof systems. SIGACT News 45(4), 59–75 (2014)

    Article  MathSciNet  Google Scholar 

  13. Grollmann, J., Selman, A.: Complexity measures for public-key cryptosystems. SIAM J. Comput. 11, 309–335 (1988)

    Article  MathSciNet  MATH  Google Scholar 

  14. Gu, X., Lutz, J., Mayordomo, E., Moser, P.: Dimension spectra of random subfractals of self-similar fractals. Ann. Pure Appl. Logic 165, 1707–1726 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  15. Hartmanis, J., Stearns, R.: On the computational complexity of algorithms. Trans. Am. Math. Soc. 117, 285–306 (1965)

    Article  MathSciNet  MATH  Google Scholar 

  16. Hausdorff, F.: Dimension und äußeres Maß. Math. Ann. 79, 157–179 (1919)

    Article  MATH  Google Scholar 

  17. Hemaspaandra, L. A., Torenvliet, L.: Theory of Semi-Feasible Algorithms. Springer, Berlin (2002)

  18. Homer, S., Selman, A. L.: Oracles for structural properties: the isomorphism problem and public-key cryptography. J. Comput. Syst. Sci. 44, 287–301 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  19. Jockusch, C. G.: Semirecursive sets and positive reducibility. Trans. Am. Math. Soc. 131, 420–436 (1968)

    Article  MathSciNet  MATH  Google Scholar 

  20. Lutz, J. H.: Resource-bounded category and measure in exponential complexity classes. Ph.D. thesis California Institute of Technology (1987)

  21. Lutz, J. H.: Category and measure in complexity classes. SIAM J. Comput. 19, 1100–1131 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  22. Lutz, J. H.: Almost everywhere high nonuniform complexity. J. Comput. Syst. Sci. 44(2), 220–258 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  23. Lutz, J. H.: The quantitative structure of exponential time. In: Hemaspaandra, L.A., Selman, A.L. (eds.) Complexity Theory Retrospective II, pp 225–254. Springer (1997)

  24. Lutz, J. H.: Dimension in complexity classes. SIAM J. Comput. 32(5), 1236–1259 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  25. Lutz, J. H.: The dimensions of individual strings and sequences. Inf. Comput. 187(1), 49–79 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  26. Lutz, J. H.: A divergence formula for randomness and dimension. Theor. Comput. Sci. 412, 166–177 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  27. Lutz, N.: Fractal intersections and products via algorithmic dimension. ACM Trans. Comput Theory 13(3) (2021)

  28. Lutz, J. H., Lutz, N.: Algorithmic information, plane Kakeya sets, and conditional dimension. ACM Trans. Comput. Theory 10(2), 7:1–7:22 (2018)

    Article  MathSciNet  MATH  Google Scholar 

  29. Lutz, J. H., Lutz, N.: Who asked us? How the theory of computing answers questions about analysis. In: Du, D., Wang, J. (eds.) Complexity and Approximation: in Memory of Ker-I Ko, pp 48–56. Springer (2020)

  30. Lutz, J. H., Mayordomo, E.: Algorithmic fractal dimensions in geometric measure theory. In: Brattka, V., Hertling, P. (eds.) Handbook of Computability and Complexity in Analysis, pp 271–302. Springer (2021)

  31. Lutz, J. H., Lutz, N., Mayordomo, E.: Extending the reach of the point-to-set principle. In: Berenbrink, P., Monmege, B. (eds.) 39th International Symposium on Theoretical Aspects of Computer Science, STACS 2022, March 15–18, 2022, Marseille, France (Virtual Conference), LIPIcs, vol. 219. https://doi.org/10.4230/LIPIcs.STACS.2022.48, pp 48:1–48:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

  32. Lutz, N., Stull, D. M.: Projection theorems using effective dimension. In: 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, August 27–31, 2018, Liverpool, UK, pp 71:1–71:15 (2018)

  33. Lutz, N., Stull, D. M.: Bounding the dimension of points on a line. Inf. Comput. 275 (2020)

  34. Martin-Löf, P.: The definition of random sequences. Inf. Control. 9, 602–619 (1966)

    Article  MathSciNet  MATH  Google Scholar 

  35. Mattila, P.: Fourier Analysis and Hausdorff Dimension. Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge (2015)

  36. Razborov, A.: On provably disjoint NP pairs. Tech. Rep. 94-006 ECCC (1994)

  37. Selman, A.: P-selective sets, tally languages, and the behavior of polynomial time reducibilities on NP. Math. Syst. Theory 13, 55–65 (1979)

    Article  MathSciNet  MATH  Google Scholar 

  38. Selman, A.: Complexity issues in cryptography. In: Computational Complexity Theory (Atlanta, GA, 1988). Proceedings of Symposia in Applied Mathematics, vol. 38, pp 92–107. American Mathematical Society (1989)

  39. Stearns, R. E., Hartmanis, J., Lewis, P.: Hierarchies of memory limited computations. In: Proceedings of the 6th Annual Symposium on Switching Circuit Theory and Logical Design, pp 179–190 (1965)

  40. Stein, E. M., Shakarchi, R.: Real Analysis: Measure Theory, Integration, and Hilbert Spaces. Princeton Lectures in Analysis. Princeton University Press, Princeton (2005)

    Book  MATH  Google Scholar 

  41. Wang, Y.: Randomness and complexity. Ph.D. thesis, Department of Mathematics University of Heidelberg (1996)

  42. Zimand, M.: Computational Complexity: a Quantitative Perspective. Elsevier, Amsterdam (2004)

    MATH  Google Scholar 

Download references

Acknowledgments

We thank an anonymous reviewer for several small corrections.

Author information

Authors and Affiliations

  1. Department of Computer Science, Iowa State University, Ames, IA, 50011, USA

    Jack H. Lutz

  2. Department of Computer Science, Swarthmore College, Swarthmore, PA, 19081, USA

    Neil Lutz

  3. Departamento de Informática e Ingeniería de Sistemas, Instituto de Investigación en Ingeniería de Aragón, Universidad de Zaragoza, 50018, Zaragoza, Spain

    Elvira Mayordomo

Authors
  1. Jack H. Lutz
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Neil Lutz
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Elvira Mayordomo
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jack H. Lutz.

Additional information

Dedicated to the memory of Alan L. Selman

Publisher’s Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This article belongs to the Topical Collection: Commemorative Issue for Alan L. Selman Guest Editors: Mitsunori Ogihara, Elvira Mayordomo, Atri Rudra

The first author’s research was supported in part by National Science Foundation grants 1545028 and 1900716. The third author’s research was supported in part by Spanish Ministry of Science, Innovation and Universities grant PID2019-104358RB-I00 and by the Science dept. of Aragon Government: Group Reference T64_20R (COSMOS research group).

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Lutz, J.H., Lutz, N. & Mayordomo, E. Dimension and the Structure of Complexity Classes. Theory Comput Syst 67, 473–490 (2023). https://doi.org/10.1007/s00224-022-10096-7

Download citation

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00224-022-10096-7

Keywords

Search

Navigation