Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR06-090 | 22nd June 2006 00:00

Non-Mitotic Sets

RSS-Feed

Abstract:

<p> We study the question of the existence of non-mitotic sets in NP. We show under various hypotheses that:</p>
<ul>
<li>1-tt-mitoticity and m-mitoticity differ on NP.</li>
<li>1-tt-reducibility and m-reducibility differ on NP.</li>
<li>There exist non-T-autoreducible sets in NP (by a result from Ambos-Spies, these sets are neither T-mitotic nor
m-mitotic).</li>
<li>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).</li>
<li>2-tt autoreducibility does not imply weak 2-tt-mitoticity.</li>
<li>1-tt-complete sets for NP are nonuniformly m-complete.</li>
</ul>



ISSN 1433-8092 | Imprint