Weak mitoticity of bounded disjunctive and conjunctive truth-table autoreducible sets (Q5918833)

It is shown that there is a sparse set in EXP that is polynomial-time 2-tt autoreducible but not even weakly polynomial-time Turing mitotic. Let me quote as a recalling of definitions: Given a notion \(r\) of reducibility, a language is \textit{\(r\)-autoreducible} if the language is reducible to itself via \(r\) where the reduction of any decision whether a given word is in the language does not query on the same input word. And two languages are \textit{\(r\)-equivalent} if any is \(r\)-reducible to the other. A language \(L\subset(0+1)^*\) is \textit{weakly mitotic} if there is a another language \(S\subset(0+1)^*\) such that \(L,S\cap L\) and \(\overline{S}\cap L\) are \(r\)-equivalent. In \textit{2-truth-table} reducibility the membership decision is reduced to a Boolean combination of two subqueries formulated in polynomial time with respect to the input length.For Turing reducibility, the membership decision for a set is reduced to computing by a Turing machine with the reduced set as an oracle. A language \(L\) is sparse if for any integer \(n\) the number of elements and the number of words of length \(n\) in the language is polynomial with respect to \(n\). The construction of the announced set involves rapidly growing maps and it illustrates quite narrowly the characteristics of the used techniques. The result generalizes previous results by \textit{C. Glaßer} et al. [Theor. Comput. Sci. 410, No. 21--23, 2011--2023 (2009; Zbl 1191.68333)], and \textit{C. Glaßer} et al. [SIAM J. Comput. 37, No. 5, 1517--1535 (2008; Zbl 1151.68024)]. Nevertheless, as a second result the authors show that any language \textit{\(k\)-conjunctive truth table}-autoreducible is mitotic and they point a list of complete classes that are mitotic as well.