Kolmogorov complexity and degrees of tally sets (Q916650): Difference between revisions

This paper is related to the questions left open by \textit{S. Tang} and \textit{R. Book} [Lect. Notes Comput. Sci. 317, 591--599 (1988; Zbl 0658.03025)]: Is \(E^p_m(TALLY)=E^p_{1-tt}(TALLY)?\) Is \(E^p_m(TALLY)=E^p_{btt}(TALLY)?\) Is there some \(k\) such that \(E^p_{k-tt}(TALLY)=E^p_{k+1-tt}(TALLY)?\) The authors introduce the notions of \(NE\) predicate (a binary predicate \(R\) such that, for some nondeterministic Turing machine \(M\) which runs in time \(2^{O(n)}\), \(R(x,y) \Leftrightarrow y\) is an accepting computation for \(x\) on \(M\)) and \(E\)-solvability of an \(NE\) predicate and shows that: \(E=E^{NP}\Rightarrow\) every \(NE\) predicate is \(E\)-solvable \(\Rightarrow\) \(E=NE\). Some characterizations of \(E\)-solvability of \(NE\) predicates are given, and the following main results are proved: 1. If all \(NE\) predicates are \(E\)-solvable, then \(E^p_{btt}(TALLY)=E^p_m(TALLY)\). 2. If not all \(NE\) predicates are \(E\)-solvable, then \(E^p_m(TALLY)\subset E^p_{1-tt}(TALLY)\). 3. If not all \(NE\) predicates are \(E\)-solvable, then for all \(k\), \(E^p_{k-tt}(TALLY)\subset E^p_{k+1-tt}(TALLY)\). The techniques used in the proofs are those provided by the machinery of generalized Kolmogorov complexity.