2021/09/13 by Jack H. Lutz, Neil Lutz, Lutz, Jack H. +3 · 1 citation
Computer Science · Mathematics · #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Mathematical Dynamics and Fractals #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2109.05956
openalex publication_date 2021/09/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We prove three results on the dimension structure of complexity classes. 1. 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 parameterize 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. 2. Every language that is ≤Pm-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 ≤Pm-hard for NP. 3. 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.