Minimal pairs and complete problems

• Verfasst von: Ambos-Spies, Klaus [VerfasserIn]
• Verfasst von: Homer, Steven [VerfasserIn]
• Verfasst von: Soare, Robert I. [VerfasserIn]
• Titel: Minimal pairs and complete problems
• Verf.angabe: Klaus Ambos-Spies, Steven Homer, Robert I. Soare
• Jahr: 1994
• Umfang: 13 S.
• Fussnoten: Elektronische Reproduktion der Druck-Ausgabe 1. April 2002 ; Gesehen am 30.05.2023
• Titel Quelle: Enthalten in: Theoretical computer science
• Ort Quelle: Amsterdam [u.a.] : Elsevier, 1975
• Jahr Quelle: 1994
• Band/Heft Quelle: 132(1994), 1, Seite 229-241
• ISSN Quelle: 1879-2294
• DOI: doi:10.1016/0304-3975(94)90234-8
• Datenträger: Online-Ressource
• Sprache: eng
• K10plus-PPN: 1846948614

Abstract

Two sets are said to form a minimal pair for polynomial many-one reductions 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 is the supremum) of a minimal pair. Our main result is that any elementary recursive set which is hard for deterministic exponential time cannot 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.