Ist P gleich dem Schnittpunkt aller superpolynomialen Zeitklassen?

21

f(n) limnnc/f(n)=0c>0

Es ist klar , dass für jede Sprache gilt , daß für jede Zeit gebunden superpolynomielle . Ich frage mich, ob das Gegenteil dieser Aussage auch zutrifft. Das heißt, wenn wir für jede superpolynomielle , impliziert dies ? Mit anderen Worten, ist es wahr, dass wobei der Schnittpunkt jedes Superpolynoms .LPLDTIME(f(n))f(n)LDTIME(f(n))f(n)LP

P=fDTIME(f(n))
f(n)
Andras Farago
quelle
1
Ein allgemeiner Ratschlag zum Schreiben von Fragen ist, dass Sie Ihre Frage (die am einfachsten zu verstehen ist) an Ihren Titel richten sollten.
Kaveh

Antworten:

31

Ja.

Tatsächlich gibt es nach dem McCreight-Meyer-Union-Theorem (Theorem 5.5 von McCreight und Meyer, 1969 , freie Version hier ) ein Ergebnis, von dem ich glaube, dass es auf Manuel Blum zurückzuführen ist, eine einzige Funktion wie . Diese Funktion ist notwendigerweise superpolynomiell, aber "gerade noch".fP=DTIME(f(n))

Das Theorem gilt allgemeiner für jedes Blum-Komplexitätsmaß und jede Union-Klasse wobei eine ce, selbst begrenzte Menge von ist gesamt berechenbare Funktionen. (Eine Menge von Funktionen ist ce, wenn es eine einzelne partielle berechenbare Funktion so dass wobei . Selbstbegrenzt bedeutet, dass es für jede endliche Teilmenge eine Funktion in , die alle dominiert fast überall. "ΦfSBLUMΦ(f(n))SSF(i,x)S={fi(x)|iN}fi(x):=F(i,x)S0SSgS0BLUMΦ"ist eine Notation, die ich noch nicht gesehen habe, aber ich mag sie :) - Ich verwende sie für das gebundene Analog einer zeitbegrenzten Komplexitätsklasse.)Φ

Joshua Grochow
quelle
12
Ich denke, der Haken ist, dass nicht ist. f
Sasho Nikolov
4
Josh, verwendet Manuels Ergebnis etwas Besonderes an der Polynomzeit? Ich meine, gilt das auch für ähnliche Zeitvereinigungsklassen?
Kaveh
2
Ich finde die folgende Tatsache faszinierend: Während es offensichtlich keine kleinste Superpolynomfunktion gibt, gibt es eine kleinste Komplexitätsklasse unter denen, die durch eine Superpolynom-Zeitgrenze definiert sind. Außerdem ist diese Klasse gleich P, in der nichts superpolynomisch ist.
Andras Farago
2
@AndrasFarago: Es ist in der Tat faszinierend, aber (glaube ich) kein Unbekannter als das Borodin-Trakhtenbrot-Gap-Theorem ( en.wikipedia.org/wiki/Gap_theorem ).
Joshua Grochow
2
@SashoNikolov: Ich würde mehr darüber nachdenken müssen, aber nach nur einem Augenblick denke ich, dass es mehr mit der Tatsache zu tun hat, dass man über TMs simulieren / diagonalisieren kann, was mehr mit ihrer zählbaren Natur und dem zu tun hat Existenz universeller Maschinen ... Insbesondere erfordern die Axiome für ein Blum-Komplexitätsmaß, dass die verschiedenen Funktionen, die das Blum-Maß definieren, berechenbar oder teilweise berechenbar sind, und dies ist der Schlüssel in all diesen Theoremen. Und beachten Sie, dass McCreight-Meyer voraussetzt, dass die Menge S selbst eine zentrale Menge von Funktionen ist, auch Schlüssel.
Joshua Grochow