{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:43:09Z","timestamp":1740109389963,"version":"3.37.3"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2022,8,17]],"date-time":"2022-08-17T00:00:00Z","timestamp":1660694400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,8,17]],"date-time":"2022-08-17T00:00:00Z","timestamp":1660694400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1545028"],"award-info":[{"award-number":["1545028"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1900716"],"award-info":[{"award-number":["1900716"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100014440","name":"Ministerio de Ciencia, Innovaci\u00f3n y Universidades","doi-asserted-by":"publisher","award":["PID2019-104358RB-I00"],"award-info":[{"award-number":["PID2019-104358RB-I00"]}],"id":[{"id":"10.13039\/100014440","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100010067","name":"Gobierno de Arag\u00f3n","doi-asserted-by":"publisher","award":["Group Reference T64\u02d920R (COSMOS research group)"],"award-info":[{"award-number":["Group Reference T64\u02d920R (COSMOS research group)"]}],"id":[{"id":"10.13039\/501100010067","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2023,6]]},"DOI":"10.1007\/s00224-022-10096-7","type":"journal-article","created":{"date-parts":[[2022,8,17]],"date-time":"2022-08-17T08:02:55Z","timestamp":1660723375000},"page":"473-490","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Dimension and the Structure of Complexity Classes"],"prefix":"10.1007","volume":"67","author":[{"given":"Jack H.","family":"Lutz","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8399-8678","authenticated-orcid":false,"given":"Neil","family":"Lutz","sequence":"additional","affiliation":[]},{"given":"Elvira","family":"Mayordomo","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,8,17]]},"reference":[{"unstructured":"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\u201321, 2001, pp 210\u2013217. IEEE Computer Society (2001)","key":"10096_CR1"},{"doi-asserted-by":"crossref","unstructured":"Bishop, C. J., Peres, Y.: Fractals in Probability and Analysis. Cambridge University Press, Cambridge (2017)","key":"10096_CR2","DOI":"10.1017\/9781316460238"},{"doi-asserted-by":"crossref","unstructured":"Buhrman, H., Longpr\u00e9, L.: Compressibility and resource bounded measure. In: Proceedings of the Thirteenth Symposium on Theoretical Aspects of Computer Science, pp 13\u201324. Springer, Berlin (1996)","key":"10096_CR3","DOI":"10.1007\/3-540-60922-9_2"},{"unstructured":"Dose, T., Gla\u00dfer, C.: NP-Completeness, Proof Systems, and Disjoint NP-Pairs. In: C. Paul, M. Bl\u00e4ser (eds.) 37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020, March 10\u201313, 2020, Montpellier, France, LIPIcs, vol. 154, pp 9:1\u20139:18. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2020)","key":"10096_CR4"},{"issue":"2","key":"10096_CR5","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/S0019-9958(84)80056-X","volume":"61","author":"S Even","year":"1984","unstructured":"Even, S., Selman, A. L., Yacobi, Y.: The complexity of promise problems with applications to public-key cryptography. Inf. Control. 61(2), 159\u2013173 (1984)","journal-title":"Inf. Control."},{"key":"10096_CR6","volume-title":"Fractal Geometry: Mathematical Foundations and Applications, 3rd edn","author":"K Falconer","year":"2014","unstructured":"Falconer, K.: Fractal Geometry: Mathematical Foundations and Applications, 3rd edn. Wiley, New York (2014)"},{"key":"10096_CR7","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/s00224-011-9326-7","volume":"51","author":"L Fortnow","year":"2012","unstructured":"Fortnow, L., Lutz, J. H., Mayordomo, E.: Inseparability and strong hypotheses for disjoint NP pairs. Theory Comput. Syst. 51, 229\u2013247 (2012)","journal-title":"Theory Comput. Syst."},{"key":"10096_CR8","doi-asserted-by":"publisher","first-page":"1369","DOI":"10.1137\/S0097539703425848","volume":"33","author":"C Gla\u00dfer","year":"2004","unstructured":"Gla\u00dfer, C., Selman, A.L., Sengupta, S., Zhang, L.: Disjoint NP-pairs. SIAM J. Comput. 33, 1369\u20131416 (2004)","journal-title":"SIAM J. Comput."},{"key":"10096_CR9","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1016\/j.ic.2005.03.003","volume":"200","author":"C Gla\u00dfer","year":"2005","unstructured":"Gla\u00dfer, C., Selman, A.L., Sengupta, S.: Reductions between disjoint NP-pairs. Inf. Comput. 200, 247\u2013267 (2005)","journal-title":"Inf. Comput."},{"key":"10096_CR10","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1016\/j.tcs.2006.10.006","volume":"370","author":"C Gla\u00dfer","year":"2007","unstructured":"Gla\u00dfer, C., Selman, A.L., Zhang, L.: Canonical disjoint NP-pairs of propositional proof systems. Theor. Comput. Sci. 370, 60\u201373 (2007)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"10096_CR11","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1142\/S012905410900670X","volume":"20","author":"C Gla\u00dfer","year":"2009","unstructured":"Gla\u00dfer, C., Selman, A.L., Zhang, L.: The informational content of canonical disjoint NP-pairs. Int. J. Found. Comput. Sci. 20(3), 501\u2013522 (2009)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"4","key":"10096_CR12","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1145\/2696081.2696095","volume":"45","author":"C Gla\u00dfer","year":"2014","unstructured":"Gla\u00dfer, C., Hughes, A., Selman, A.L., Wisiol, N.: Disjoint NP-pairs and propositional proof systems. SIGACT News 45(4), 59\u201375 (2014)","journal-title":"SIGACT News"},{"key":"10096_CR13","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1137\/0217018","volume":"11","author":"J Grollmann","year":"1988","unstructured":"Grollmann, J., Selman, A.: Complexity measures for public-key cryptosystems. SIAM J. Comput. 11, 309\u2013335 (1988)","journal-title":"SIAM J. Comput."},{"key":"10096_CR14","doi-asserted-by":"publisher","first-page":"1707","DOI":"10.1016\/j.apal.2014.07.001","volume":"165","author":"X Gu","year":"2014","unstructured":"Gu, X., Lutz, J., Mayordomo, E., Moser, P.: Dimension spectra of random subfractals of self-similar fractals. Ann. Pure Appl. Logic 165, 1707\u20131726 (2014)","journal-title":"Ann. Pure Appl. Logic"},{"key":"10096_CR15","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1090\/S0002-9947-1965-0170805-7","volume":"117","author":"J Hartmanis","year":"1965","unstructured":"Hartmanis, J., Stearns, R.: On the computational complexity of algorithms. Trans. Am. Math. Soc. 117, 285\u2013306 (1965)","journal-title":"Trans. Am. Math. Soc."},{"key":"10096_CR16","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/BF01457179","volume":"79","author":"F Hausdorff","year":"1919","unstructured":"Hausdorff, F.: Dimension und \u00e4u\u00dferes Ma\u00df. Math. Ann. 79, 157\u2013179 (1919)","journal-title":"Math. Ann."},{"doi-asserted-by":"crossref","unstructured":"Hemaspaandra, L. A., Torenvliet, L.: Theory of Semi-Feasible Algorithms. Springer, Berlin (2002)","key":"10096_CR17","DOI":"10.1007\/978-3-662-05080-4"},{"key":"10096_CR18","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/0022-0000(92)90023-C","volume":"44","author":"S Homer","year":"1992","unstructured":"Homer, S., Selman, A. L.: Oracles for structural properties: the isomorphism problem and public-key cryptography. J. Comput. Syst. Sci. 44, 287\u2013301 (1992)","journal-title":"J. Comput. Syst. Sci."},{"key":"10096_CR19","doi-asserted-by":"publisher","first-page":"420","DOI":"10.1090\/S0002-9947-1968-0220595-7","volume":"131","author":"CG Jockusch","year":"1968","unstructured":"Jockusch, C. G.: Semirecursive sets and positive reducibility. Trans. Am. Math. Soc. 131, 420\u2013436 (1968)","journal-title":"Trans. Am. Math. Soc."},{"doi-asserted-by":"crossref","unstructured":"Lutz, J. H.: Resource-bounded category and measure in exponential complexity classes. Ph.D. thesis California Institute of Technology (1987)","key":"10096_CR20","DOI":"10.1109\/PSCT.1987.10319257"},{"key":"10096_CR21","doi-asserted-by":"publisher","first-page":"1100","DOI":"10.1137\/0219076","volume":"19","author":"JH Lutz","year":"1990","unstructured":"Lutz, J. H.: Category and measure in complexity classes. SIAM J. Comput. 19, 1100\u20131131 (1990)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"10096_CR22","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1016\/0022-0000(92)90020-J","volume":"44","author":"JH Lutz","year":"1992","unstructured":"Lutz, J. H.: Almost everywhere high nonuniform complexity. J. Comput. Syst. Sci. 44(2), 220\u2013258 (1992)","journal-title":"J. Comput. Syst. Sci."},{"doi-asserted-by":"crossref","unstructured":"Lutz, J. H.: The quantitative structure of exponential time. In: Hemaspaandra, L.A., Selman, A.L. (eds.) Complexity Theory Retrospective II, pp 225\u2013254. Springer (1997)","key":"10096_CR23","DOI":"10.1007\/978-1-4612-1872-2_10"},{"issue":"5","key":"10096_CR24","doi-asserted-by":"publisher","first-page":"1236","DOI":"10.1137\/S0097539701417723","volume":"32","author":"JH Lutz","year":"2003","unstructured":"Lutz, J. H.: Dimension in complexity classes. SIAM J. Comput. 32(5), 1236\u20131259 (2003)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"10096_CR25","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/S0890-5401(03)00187-1","volume":"187","author":"JH Lutz","year":"2003","unstructured":"Lutz, J. H.: The dimensions of individual strings and sequences. Inf. Comput. 187(1), 49\u201379 (2003)","journal-title":"Inf. Comput."},{"key":"10096_CR26","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1016\/j.tcs.2010.09.005","volume":"412","author":"JH Lutz","year":"2011","unstructured":"Lutz, J. H.: A divergence formula for randomness and dimension. Theor. Comput. Sci. 412, 166\u2013177 (2011)","journal-title":"Theor. Comput. Sci."},{"doi-asserted-by":"crossref","unstructured":"Lutz, N.: Fractal intersections and products via algorithmic dimension. ACM Trans. Comput Theory 13(3) (2021)","key":"10096_CR27","DOI":"10.1145\/3460948"},{"issue":"2","key":"10096_CR28","doi-asserted-by":"publisher","first-page":"7:1","DOI":"10.1145\/3201783","volume":"10","author":"JH Lutz","year":"2018","unstructured":"Lutz, J. H., Lutz, N.: Algorithmic information, plane Kakeya sets, and conditional dimension. ACM Trans. Comput. Theory 10(2), 7:1\u20137:22 (2018)","journal-title":"ACM Trans. Comput. Theory"},{"doi-asserted-by":"crossref","unstructured":"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\u201356. Springer (2020)","key":"10096_CR29","DOI":"10.1007\/978-3-030-41672-0_4"},{"doi-asserted-by":"crossref","unstructured":"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\u2013302. Springer (2021)","key":"10096_CR30","DOI":"10.1007\/978-3-030-59234-9_8"},{"doi-asserted-by":"publisher","unstructured":"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\u201318, 2022, Marseille, France (Virtual Conference), LIPIcs, vol. 219. https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2022.48, pp 48:1\u201348:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2022)","key":"10096_CR31","DOI":"10.4230\/LIPIcs.STACS.2022.48"},{"unstructured":"Lutz, N., Stull, D. M.: Projection theorems using effective dimension. In: 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, August 27\u201331, 2018, Liverpool, UK, pp 71:1\u201371:15 (2018)","key":"10096_CR32"},{"doi-asserted-by":"crossref","unstructured":"Lutz, N., Stull, D. M.: Bounding the dimension of points on a line. Inf. Comput. 275 (2020)","key":"10096_CR33","DOI":"10.1016\/j.ic.2020.104601"},{"key":"10096_CR34","doi-asserted-by":"publisher","first-page":"602","DOI":"10.1016\/S0019-9958(66)80018-9","volume":"9","author":"P Martin-L\u00f6f","year":"1966","unstructured":"Martin-L\u00f6f, P.: The definition of random sequences. Inf. Control. 9, 602\u2013619 (1966)","journal-title":"Inf. Control."},{"doi-asserted-by":"crossref","unstructured":"Mattila, P.: Fourier Analysis and Hausdorff Dimension. Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge (2015)","key":"10096_CR35","DOI":"10.1017\/CBO9781316227619"},{"doi-asserted-by":"crossref","unstructured":"Razborov, A.: On provably disjoint NP pairs. Tech. Rep. 94-006 ECCC (1994)","key":"10096_CR36","DOI":"10.7146\/brics.v1i36.21607"},{"key":"10096_CR37","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/BF01744288","volume":"13","author":"A Selman","year":"1979","unstructured":"Selman, A.: P-selective sets, tally languages, and the behavior of polynomial time reducibilities on NP. Math. Syst. Theory 13, 55\u201365 (1979)","journal-title":"Math. Syst. Theory"},{"doi-asserted-by":"crossref","unstructured":"Selman, A.: Complexity issues in cryptography. In: Computational Complexity Theory (Atlanta, GA, 1988). Proceedings of Symposia in Applied Mathematics, vol. 38, pp 92\u2013107. American Mathematical Society (1989)","key":"10096_CR38","DOI":"10.1090\/psapm\/038\/1020811"},{"doi-asserted-by":"crossref","unstructured":"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\u2013190 (1965)","key":"10096_CR39","DOI":"10.1109\/FOCS.1965.11"},{"key":"10096_CR40","doi-asserted-by":"publisher","DOI":"10.1515\/9781400835560","volume-title":"Real Analysis: Measure Theory, Integration, and Hilbert Spaces. Princeton Lectures in Analysis","author":"EM Stein","year":"2005","unstructured":"Stein, E. M., Shakarchi, R.: Real Analysis: Measure Theory, Integration, and Hilbert Spaces. Princeton Lectures in Analysis. Princeton University Press, Princeton (2005)"},{"unstructured":"Wang, Y.: Randomness and complexity. Ph.D. thesis, Department of Mathematics University of Heidelberg (1996)","key":"10096_CR41"},{"key":"10096_CR42","volume-title":"Computational Complexity: a Quantitative Perspective","author":"M Zimand","year":"2004","unstructured":"Zimand, M.: Computational Complexity: a Quantitative Perspective. Elsevier, Amsterdam (2004)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-022-10096-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-022-10096-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-022-10096-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,1]],"date-time":"2024-10-01T22:27:10Z","timestamp":1727821630000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-022-10096-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,17]]},"references-count":42,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,6]]}},"alternative-id":["10096"],"URL":"https:\/\/doi.org\/10.1007\/s00224-022-10096-7","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2022,8,17]]},"assertion":[{"value":"29 June 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 August 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}