Dimension and the structure of complexity classes

Lutz, Jack H. ; Lutz, Neil ; Mayordomo, Elvira (Universidad de Zaragoza)

Resumen: 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.

Idioma: Inglés

DOI: 10.1007/s00224-022-10096-7

Año: 2023

Publicado en: THEORY OF COMPUTING SYSTEMS 67 (2023), 473-490
ISSN: 1432-4350

Factor impacto JCR: 0.6 (2023)

Categ. JCR: MATHEMATICS rank: 263 / 489 = 0.538 (2023) - Q3 - T2
Categ. JCR: COMPUTER SCIENCE, THEORY & METHODS rank: 117 / 143 = 0.818 (2023) - Q4 - T3

Factor impacto CITESCORE: 1.9 - Theoretical Computer Science (Q3) - Computational Theory and Mathematics (Q3)

Factor impacto SCIMAGO: 0.661 - Theoretical Computer Science (Q2) - Computational Theory and Mathematics (Q2)

Financiación: info:eu-repo/grantAgreement/ES/DGA/T64-20R
Financiación: info:eu-repo/grantAgreement/ES/MICIU/PID2019-104358RB-I00

Tipo y forma: Artículo (PostPrint)

Área (Departamento): Área Lenguajes y Sistemas Inf. (Dpto. Informát.Ingenie.Sistms.)