Abstract/Details

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

Rubinstein, Roy Steven.   Northeastern University ProQuest Dissertations & Theses,  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)


Subject
Computer science
Classification
0984: Computer science
Identifier / keyword
Applied sciences
Title
Structural complexity classes of sparse sets: Intractability, data compression and printability
Author
Rubinstein, Roy Steven
Number of pages
79
Degree date
1988
School code
0160
Source
DAI-B 49/12, Dissertation Abstracts International
ISBN
979-8-206-73572-7
University/institution
Northeastern University
University location
United States -- Massachusetts
Degree
Ph.D.
Source type
Dissertation or Thesis
Language
English
Document type
Dissertation/Thesis
Dissertation/thesis number
8904853
ProQuest document ID
303720650
Copyright
Database copyright ProQuest LLC; ProQuest does not claim copyright in the individual underlying works.
Document URL
https://www.proquest.com/docview/303720650