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.
ASJC Scopus subject areas
- Theoretical Computer Science
- Information Systems
- Computer Science Applications
- Computational Theory and Mathematics