MINIMAL PAIRS AND COMPLETE PROBLEMS

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.