This proposal will support both new and continuing investigations into structural properties of complete sets, randomness in computation, and internal structure such as a self-reducibility of feasible sets. The purposes are: to continue successful work on the Berman-Hartmanis isomorphism conjecture with particular emphasis on characterizing complexity theoretic assumptions for the isomorphism conjecture to hold or fail; to continue recent investigations into random oracles that have yielded an interesting new proof technique and hold promise of stronger results; and to examine the structural complexity consequences of checkability, coherence, random self-reducibility, and other recently introduced concepts related to self-reducibility.//
