Autoreducibility of complete sets under polynomial-time reductions
Nguyen, Dung Tien
MetadataShow full item record
This research focuses on autoreducibility and mitoticity of complete sets for NEXP. A set A is autoreducible if A is reducible to A via an oracle Turing machine M such that M never queries x on input x . Ambos-Spies introduced the polynomial-time variant of autoreducibility, where the oracle Turing machine now runs in polynomial time. A set A is ≤r-mitotic if there is a set S in P such that all sets A , the intersection of A and the complement of S , and the intersection of A and S are reducible to each other by the polynomial-time reduction ≤ r . Again, ≤ r can be any polynomial-time reduction and so each notion of reduction induces a notion of mitoticity. Autoreducibility and mitoticity capture the information redundancy of complete sets; while autoreducibility captures local redundancy, mitoticity captures global redundancy. Studying structural properties of complete sets, especially autoreducibility and mitoticity, helps to understand deeply the characteristics of a particular complexity class, and hence hopefully can separate one from another. With this motivation in mind, we study autoreducibility and mitoticity questions extensively for NEXP. First we approach the question of under what reductions all complete sets for NEXP are autoreducible. Then we take another slightly different direction: we want to understand in what situation a complete set for NEXP is no longer autoreducible. In this direction, we discover that resolving certain autoreducibility questions either positively or negatively lead to interesting class separation results. Finally, by tuning some techniques to show many-one mitoticity of complexity classes, we can obtain mitoticity results for EXP and PSPACE under polynomial-time and log-space disjunctive-truth-table and conjunctive-truth-table reductions.