Dimension And The Structure Of Complexity Classes

Document Type

Article

Publication Date

6-1-2023

Published In

Theory Of Computing Systems

Abstract

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 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. (2) Every language that is ≤ (P/m)-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 ≤ (P/m)-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.

Keywords

Algorithmic dimensions, p-selective sets, Disjoint NP pairs, Resource-bounded dimension

Link to Full Text

Share

COinS