131314
20240731103312.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
263 / 489 = 0.538
2023
Q3
T2
COMPUTER SCIENCE, THEORY & METHODS
117 / 143 = 0.818
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-07-31-09:39:54
ARTICLE