Kann man entscheiden, ob ein bestimmter Algorithmus asymptotisch optimal ist?

Gibt es einen Algorithmus für das folgende Problem:

Bei einer Turing - Maschine , die eine Sprache entscheidet , Gibt es eine Turing - Maschine entscheiden , so dass ?$M_1$$L$
$M_2$$L$$t_2(n) = o(t_1(n))$

Die Funktionen und sind die Worst-Case-Laufzeiten der Turing-Maschinen bzw. .$t_1$$t_2$$M_1$$M_2$

Was ist mit der Komplexität des Raums?

Hier ist ein einfaches Argument, um zu zeigen, dass sie nicht entscheidbar sind, dh es gibt keine Algorithmen, mit denen überprüft werden kann, ob ein bestimmter Algorithmus hinsichtlich seiner Laufzeit oder Speichernutzung optimal ist.

Wir reduzieren das Problem des Anhaltens auf leerem Band auf Ihr Problem der Laufzeitoptimierung.

Sei eine gegebene Turingmaschine. Sei N die folgende Turingmaschine:$M$

: am Eingang n 1. Führen Sie M für (höchstens) n Schritteauf einem leeren Band aus. 2. Wenn M nicht in n Schritten anhält, führen Sie eine Schleife der Größe 2 n aus und geben Sie NO zurück. 3. Andernfalls geben Sie JA zurück.$N$$n$
$M$$n$
$M$$n$$2^n$

Es gibt zwei Fälle:

1. Wenn nicht auf leerem Band anhält, läuft die Maschine N für Θ ( 2 n ) Schritte am Eingang n . Die Laufzeit beträgt also Θ ( 2 n ) . In diesem Fall ist N offensichtlich nicht optimal.$M$$N$$\Theta(2^n)$$n$$\Theta(2^n)$$N$

2. Wenn auf einem leeren Band anhält, läuft die Maschine N für eine konstante Anzahl von Schritten für alle ausreichend großen n , sodass die Laufzeit O ( 1 ) ist . In diesem Fall ist N offensichtlich optimal.$M$$N$$n$$O(1)$$N$

Zusamenfassend:

Außerdem können wir mit dem Code für den Code für N berechnen . Daher haben wir eine Reduzierung vom Problem des Anhaltens auf leerem Band zum Problem der Laufzeitoptimierung. Wenn wir entscheiden könnten, ob eine gegebene Turingmaschine N optimal ist, könnten wir die obige Reduzierung verwenden, um zu prüfen, ob eine gegebene Maschine M auf einem leeren Band anhält. Da das Anhalten auf leerem Band nicht entschieden werden kann, ist auch Ihr Problem nicht zu entscheiden.$M$$N$$N$$M$

Ein ähnliches Argument kann für den Speicherplatz verwendet werden, dh es ist auch unentscheidbar zu prüfen, ob eine bestimmte Turing-Maschine hinsichtlich des von ihr verwendeten Speicherplatzes optimal ist.

Eine noch stärkere Aussage ist wahr: Wir können nicht entscheiden, ob eine bestimmte berechenbare Funktion eine Obergrenze für die zeitliche Komplexität der Berechnung einer bestimmten berechenbaren Funktion darstellt. Ähnliches gilt für den Weltraum. Das heißt, selbst die grundlegende Komplexitätstheorie kann nicht durch Algorithmen automatisiert werden (was für Komplexitätstheoretiker eine gute Nachricht sein kann;).

Wie andere bereits erwähnt haben, lautet die Antwort nein.

Aber es gibt einen interessanten Artikel von Blum " Eine maschinenunabhängige Theorie der Komplexität rekursiver Funktionen ". Er zeigte, dass es einige Funktionen mit der Eigenschaft gibt, dass unabhängig davon, wie schnell ein Programm diese Funktionen berechnet, ein anderes Programm existiert, um sie sehr viel schneller zu berechnen .

ein sehr schönes Hotel!

Ha! Wäre die Antwort ja, würden wir in einer anderen Welt leben.

Stellen Sie sich vor, die Antwort auf Ihre Frage wäre ja (und natürlich kannten wir den Algorithmus , der Ihre Frage beantworten würde). Dann könnten wir für jeden Algorithmus A für Sprache L (unter Verwendung von A 0 ) feststellen, ob A optimal ist oder nicht.$A_0$$A$$L$$A_0$$A$

Leider ist dies nicht möglich, und ich persönlich denke, dass der Nachweis (nicht trivialer) Optimalität das interessanteste (und schwierigste) Problem in der Informatik ist. Soweit ich weiß - ich würde mich freuen, korrigiert zu werden - gibt es kein Optimalitätsergebnis für ein Polynomproblem (außer den trivialen Optimalitätsergebnissen von Algorithmen, deren Zeit proportional zur Eingabegröße ist).