The notion of “lowness” was introduced in computational complexity theory by U. Schöning [J. Comput. Syst. Sci. 27, 14-28 (1983; Zbl 0515.68046)] who studied sets in the class NP. This notion may be interpreted as setting an upper bound on the amount of information that can be encoded by a set. Here ideas from previous studies are incorporated in order to capture the notion of a set being exponentially low.
The main result asserts the existence of a sparse set E such that \(DEXT(E)=DEXT\), i.e., E is “exponentially low”, but E is not in the class P. In contrast, any set with small generalized Kolmogorov complexity that is exponentially low must be in the class P. In addition, we show that for each \(k\geq 2\), any sparse set S that is low with respect to the class \(\Sigma^ E_ k\) of the exponential-time hierarchy (i.e., \(\Sigma^ E_ k(S)=\Sigma^ E_ k)\) must be in the class \(\Sigma^ P_ k\) of the polynomial-time hierarchy. Similarly, for each \(k\geq 4\), any set with polynomial-size circuits that is low with respect to the class \(\Sigma^ E_ k\) must be in the class \(\Sigma^ P_ k\).