Splitting NP-complete sets infinitely (Q6551699)

In [Theor. Comput. Sci. 410, No. 21--23, 2011--2023 (2009; Zbl 1191.68333); SIAM J. Comput. 37, No. 5, 1517--1535 (2008; Zbl 1151.68024)] \textit{C. Glaßer} et al. proved that, with respect to the many-one reduction, an NP-complete language can be partitioned into two NP-complete languages, and obviously this result is extended to partitions consisting of finitely many NP-complete languages. In the current paper it is proved that this result may be extended to recursive partitions consisting of infinitely many NP-complete languages. The provided proof is rather technical. The authors consider two signals, Rej, for reject, and Acc, for accept. A reduction of a language \(A\) into a language \(B\) is a map \(\phi\) such that \(\phi(A)\subset B\cup\{\mbox{Acc}\}\) and \(\phi(A^c)\subset B^c\cup\{\mbox{Rej}\}\), which is equivalent to the conventional definition whenever \(A\) is non-trivial, namely when neither \(A\) nor \(A^c\) are monads. Two languages are equivalent under a reduction if each of them is reducible to the other. It is recalled that any autoreducible language is mitotic: it can be split into two dijoint languages equivalent under reduction to the whole language. A splitting map for a language is valued in \(\{0,1\}\cup\{\mbox{Rej},\mbox{Acc}\}\), takes the value Acc only for words in the language and takes the value Rej only for words in the complement of the language. A flipping map for a splitting map is an autoreduction that switches values in \(\{0,1\}\). Then it is shown that if there is a splitting function with a corresponding flipping map and these are polynomial-time computable then the language is mitotic. The authors state sufficient conditions, in terms of membership proofs of a language, for a language to be autoreducible, and thereafter explain how to obtain polynomial-time computable splitting functions and corresponding flipping maps. It is proved that any NP-complete language satisfies these conditions. An argument by induction serves to prove the main result in the paper.