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
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;
Conference_Titel :
Structure in Complexity Theory Conference, 1988. Proceedings., Third Annual
Conference_Location :
Washington, DC
Print_ISBN :
0-8186-0866-8
DOI :
10.1109/SCT.1988.5269