DocumentCode
3508504
Title
Kolmogorov complexity and degrees of tally sets
Author
Allender, Eric ; Watanabe, Osamu
Author_Institution
Dept. of Comput. Sci., Rutgers Univ., New Brunswick, NJ, USA
fYear
1988
fDate
14-17 Jun 1988
Firstpage
102
Lastpage
111
Abstract
A recent paper by S. Tang and R. Book (1988) initiated a study of the classes of sets which are equivalent to tally sets or sparse sets, under varying notions of reducibility. A number of interesting results are proved, and many additional questions are posed and left open. The authors investigate some of these questions and show that they are equivalent to each other and are closely related to other important open questions in complexity theory
Keywords
Turing machines; computational complexity; Kolmogorov complexity; Turing machines; degrees of tally sets; reducibility; sparse sets; Books; Circuits; Complexity theory; Computer science; Computer science education; Mathematics; Polynomials;
fLanguage
English
Publisher
ieee
Conference_Titel
Structure in Complexity Theory Conference, 1988. Proceedings., Third Annual
Conference_Location
Washington, DC
Print_ISBN
0-8186-0866-8
Type
conf
DOI
10.1109/SCT.1988.5269
Filename
5269
Link To Document