000131314 001__ 131314 000131314 005__ 20240731103312.0 000131314 0247_ $$2doi$$a10.1007/s00224-022-10096-7 000131314 0248_ $$2sideral$$a130096 000131314 037__ $$aART-2023-130096 000131314 041__ $$aeng 000131314 100__ $$aLutz, Jack H. 000131314 245__ $$aDimension and the structure of complexity classes 000131314 260__ $$c2023 000131314 5060_ $$aAccess copy available to the general public$$fUnrestricted 000131314 5203_ $$aWe 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. 000131314 536__ $$9info:eu-repo/grantAgreement/ES/DGA/T64-20R$$9info:eu-repo/grantAgreement/ES/MICIU/PID2019-104358RB-I00 000131314 540__ $$9info:eu-repo/semantics/openAccess$$aAll rights reserved$$uhttp://www.europeana.eu/rights/rr-f/ 000131314 590__ $$a0.6$$b2023 000131314 592__ $$a0.661$$b2023 000131314 591__ $$aMATHEMATICS$$b263 / 489 = 0.538$$c2023$$dQ3$$eT2 000131314 593__ $$aTheoretical Computer Science$$c2023$$dQ2 000131314 591__ $$aCOMPUTER SCIENCE, THEORY & METHODS$$b117 / 143 = 0.818$$c2023$$dQ4$$eT3 000131314 593__ $$aComputational Theory and Mathematics$$c2023$$dQ2 000131314 594__ $$a1.9$$b2023 000131314 655_4 $$ainfo:eu-repo/semantics/article$$vinfo:eu-repo/semantics/acceptedVersion 000131314 700__ $$aLutz, Neil 000131314 700__ $$0(orcid)0000-0002-9109-5337$$aMayordomo, Elvira$$uUniversidad de Zaragoza 000131314 7102_ $$15007$$2570$$aUniversidad de Zaragoza$$bDpto. Informát.Ingenie.Sistms.$$cÁrea Lenguajes y Sistemas Inf. 000131314 773__ $$g67 (2023), 473-490$$pTheor. Comput. Syst.$$tTHEORY OF COMPUTING SYSTEMS$$x1432-4350 000131314 8564_ $$s321854$$uhttps://zaguan.unizar.es/record/131314/files/texto_completo.pdf$$yPostprint 000131314 8564_ $$s1227514$$uhttps://zaguan.unizar.es/record/131314/files/texto_completo.jpg?subformat=icon$$xicon$$yPostprint 000131314 909CO $$ooai:zaguan.unizar.es:131314$$particulos$$pdriver 000131314 951__ $$a2024-07-31-09:39:54 000131314 980__ $$aARTICLE