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

Rubinstein, Roy Steven. 
 Northeastern University ProQuest Dissertations Publishing,  1988. 8904853.

Abstract (summary)

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.

Indexing (details)

Computer science
0984: Computer science
Identifier / keyword
Applied sciences
Structural complexity classes of sparse sets: Intractability, data compression and printability
Rubinstein, Roy Steven
Number of pages
Degree date
School code
DAI-B 49/12, Dissertation Abstracts International
Place of publication
Ann Arbor
Country of publication
United States
Northeastern University
University location
United States -- Massachusetts
Source type
Dissertation or Thesis
Document type
Dissertation/thesis number
ProQuest document ID
Database copyright ProQuest LLC; ProQuest does not claim copyright in the individual underlying works.
Document URL