ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > KEYWORD > COMPLETENESS NOTIONS:
Reports tagged with completeness notions:
TR06-090 | 22nd June 2006
Christian Glaßer, Alan L. Selman, Stephen Travers, Liyu Zhang

Non-Mitotic Sets

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 >>>



ISSN 1433-8092 | Imprint