Two sets are said to form a minimal pair for polynomial many-one reduc
tions if neither set is in P and the only sets which are polynomially
reducible (via polynomial many-one reductions) to both sets are in P.
We consider the question of which complete sets can be the top (that i
s the supremum) of a minimal pair. Our main result is that any element
ary recursive set which is hard for deterministic exponential time can
not be the top of a minimal pair. Hence in particular any complete set
for an elementary recursive class containing exponential time cannot
be such a supremum. For NP-complete sets the problem remains open. We
show here that it is oracle dependent. This is the first example of an
oracle dependent property which is completely degree theoretic.