Splittings, Robustness, and Structure of Complete Sets
Harry Buhrman, Albrecht Hoene, Leen Torenvliet · SIAM Journal on Computing · 1998
We investigate the structure of EXP-complete and hard sets under various kinds of reductions. In particular, we are interested in the way in which information that makes the set complete is stored in the set. We study for various types of reductions the question of whether the set difference A-S for a hard set A and a sparse set S is still hard. We also address the question of which complete sets A can be split into sets A 1 and A 2 such that $A\equiv^P_r A_1\equiv^P_r A_2$ for reduction type r, i.e., which complete sets are mitotic. We obtain both positive and negative answers to these questions depending on the reduction type and the structure of the sparse set.