Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
437782 | Theoretical Computer Science | 2011 | 13 Pages |
Abstract
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.•T-autoreducibility and T-mitoticity differ on NP (this contrasts the situation in the recursion theoretic setting, where Ladner showed that autoreducibility and mitoticity coincide).•2-tt-autoreducibility does not imply weak 2-tt-mitoticity (from this it follows that autoreducibility and mitoticity are not equivalent for all reducibilities between 2-tt and T, although the notions coincide for m- and 1-tt-reducibility).
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics