Structural complexity classes of sparse sets: Intractability, data compression and printability

Computational complexity theory is the study of the quantitative aspects of computing. In particular, the time and space needed for the recognition of various sets has been of primary importance. Associated with this is the study of various structural properties of sets. These structural properties have known important relationships to computational complexities, but they do not correlate exactly. Thus, a direct connection between structural properties and computational complexity does not exist. We will call classes of sets defined by possessing these properties structural complexity classes. The structural complexity classes most commonly used are the class of sparse sets and the class of tally sets.

This thesis discusses various structural complexity classes (including sparse sets, sets with small generalized Kolmogorov complexity, P-printable sets, and self-P-printable sets), their interrelationships, and their relationships with computational complexity classes.

One result presented here is that a set is P-printable if and only if it is P-isomorphic to a tally language in P, if and only if it is in P and has small generalized Kolmogorov complexity. This has the important corollary that sets of small generalized Kolmogorov complexity are precisely those that are P-isomorphic to a tally language.

Another result is that sparse non-self-P-printable sets do exist, and some of the necessary and sufficient conditions for their existence at certain levels of the polynomial hierarchy explored. It is also shown that every self-P-printable set is polynomial time Turing equivalent to a tally set, and the requirements and ramifications of the class of self-P-printable sets being precisely the class of sparse sets that are polynomial time Turing equivalent to a tally set are discussed.

Characterizations of the sparse sets in terms of self-printability and self-relativized generalized Kolmogorov complexity are also presented. Relativizations involving FewP are also shown, indicating that many of the questions raised here will be difficult to answer, as there are different relativizations under which these questions are answered in opposite ways.