SIGACT news complexity theory column 64
Lane A. Hemaspaandra · ACM SIGACT News · 2009
Autoreducibility and mitoticity express weak forms of redundancy of information that a set might possess. We describe many results known about these concepts. Mitoticity always implies autoreducibility, but the converse holds in some situations and fails in others. Among the results we describe are that NP-complete sets are many-one autoreducible and that every many-one autoreducible set is many-one mitotic. In particular, every infinite NPcomplete set splits by a set in P into two disjoint, infinite NP-complete set.