Kolmogorov complexity and degrees of tally sets

Eric Allender, Osamu Watanabe

Research output: Contribution to journalArticlepeer-review

9 Scopus citations

Abstract

We show that either Epm(TALLY)=Epbtt(TALLY)orEpm(TALLY)⊂Ep1-tt(TALLY)⊂Ep2-tt(TALLY)⊂Ep3-tt(TALLY)..., where Erp(TALLY) denotes the class of sets which are equivalent to a tally set under ≤rp reductions. Furthermore, the question of whether or not Emp(TALLY) = Ebttp(TALLY) is equivalent to the question of whether or not NE predicates can be solved in deterministic exponential time. The proofs use the techniques of generalized Kolmogorov complexity. As corollaries to some of the main results, we obtain new results about the Kolmogorov complexity of sets in P.

Original languageEnglish (US)
Pages (from-to)160-178
Number of pages19
JournalInformation and Computation
Volume86
Issue number2
DOIs
StatePublished - Jun 1990

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Kolmogorov complexity and degrees of tally sets'. Together they form a unique fingerprint.

Cite this