We study the question of the existence of non-mitotic sets in NP. We show under various hypotheses that:
- 1-tt-mitoticity and m-mitoticity differ on NP.
- 1-tt-reducibility and m-reducibility differ on NP.
- There exist non-T-autoreducible sets in NP (by a result from Ambos-Spies, these sets are neither T-mitotic nor m-mitotic).
...
more >>>