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 :
بازگشت