131314 20241125101126.0 doi 10.1007/s00224-022-10096-7 sideral 130096 ART-2023-130096 eng Lutz, Jack H. Dimension and the structure of complexity classes 2023 Access copy available to the general public Unrestricted We prove three results on the dimension structure of complexity classes. 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. Every language that is =mP-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 =mP-hard for NP. 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. info:eu-repo/grantAgreement/ES/DGA/T64-20R info:eu-repo/grantAgreement/ES/MICIU/PID2019-104358RB-I00 info:eu-repo/semantics/openAccess All rights reserved http://www.europeana.eu/rights/rr-f/ 0.6 2023 MATHEMATICS 264 / 490 = 0.539 2023 Q3 T2 COMPUTER SCIENCE, THEORY & METHODS 117 / 144 = 0.812 2023 Q4 T3 0.661 2023 Theoretical Computer Science 2023 Q2 Computational Theory and Mathematics 2023 Q2 1.9 2023 info:eu-repo/semantics/article info:eu-repo/semantics/acceptedVersion Lutz, Neil Mayordomo, Elvira Universidad de Zaragoza (orcid)0000-0002-9109-5337 5007 570 Universidad de Zaragoza Dpto. Informát.Ingenie.Sistms. Área Lenguajes y Sistemas Inf. 67 (2023), 473-490 Theor. Comput. Syst. THEORY OF COMPUTING SYSTEMS 1432-4350 321854 http://zaguan.unizar.es/record/131314/files/texto_completo.pdf Postprint 1227514 http://zaguan.unizar.es/record/131314/files/texto_completo.jpg?subformat=icon icon Postprint oai:zaguan.unizar.es:131314 articulos driver 2024-11-22-11:57:36 ARTICLE