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.

A set is P-selective (Selman, 1979) if there is a polynomial-time semidecision algorithm for the set — an algorithm that given any two strings decides which is “more likely” to be in the set. This paper establishes a strict hierarchy among the various reductions and equivalences to P-selective sets.

This paper completely characterizes the complexity of implicit membership testing in terms of the well-known complexity class OptP, optimization polynomial time, and concludes that many complex sets have polynomial-time implicit membership tests.

Sets whose members are enumerated by some Turing machine are called recursively enumerable. We define a set to be polynomially enumerable by iteration if its members are efficiently enumerated by iterated application of some Turing machine. We prove that many complex sets—including all exponential-time complete sets, all NP-complete sets yet obtained by direct construction, and the complements of all such sets—are polynomially enumerable by iteration. These results follow from more general results. In fact, we show that all recursively enumerable sets that are ⪯p1si-self-reducible are polynomially enumerable by iterations, and that all recursive sets that are p1si-self-reducible are bi-enumerable. We also show that when the ⪯p1si-self-reduction is via a function whose inverse is computable in polynomial time, then the above results hold with the polynomial enumeration given by a function whose inverse is computable in polynomial time. In the final section of the paper we show that no NP-complete set can be iteratively enumerated in lexicographically increasing order unless the polynomial time hierarchy collapses to NP. We also show that the sets that are monotonically bi-enumerable are “essentially” the same as the sets in parity polynomial time.