Gibt es entscheidbare Probleme, für die wir für keinen Algorithmus Zeitgrenzen festlegen können?

Gibt es entscheidbare Probleme, so dass wir für keinen Algorithmus, der das Problem löst, eine Zeitgrenze als Funktion der Länge n der Eingabeinstanz angeben können?

Ich bin zu dieser Frage gekommen, weil ich über Folgendes nachgedacht habe:

Angenommen, wir haben ein rekursiv aufzählbares, aber unentscheidbares Problem. Angenommen, ich bin eine "Ja" -Instanz des Problems. Dann können wir für keinen Algorithmus, der die "Ja" -Instanzen des Problems identifiziert, eine Zeitgrenze in Bezug auf die Größe n von I angeben. Wenn wir eine solche Zeitgrenze angeben könnten, könnten wir das Problem entscheiden, wie wir es einfach könnten zu dem schluss kommen, dass ich ein "nein" -instanz bin, wenn die zeitgrenze überschritten wird.

Da wir keine Zeit für rekursiv aufzählbare, unentscheidbare Probleme angeben können (für die Rechenzeit für "Ja" -Instanzen), habe ich mich gefragt, ob es auch entscheidbare Probleme gibt, für die wir keine Zeit angeben können.

Für jeden Algorithmus , der an einer Klasse von Eingängen I n endet , können wir die Funktion seiner Laufzeiten definieren : f ( n ) = max i ∈ I n ( n ) t i m e ( A ( i ) ) , wobei I n ( n ) ist die Klasse von Eingaben der Länge n und t i m e ( A ( i $A$$\mathsf{In}$

Wenn wir einfache algebraische Begriffe (ohne jegliche Rekursion) als Definition von Prägnanz verwenden, dann lautet die Antwort meines Erachtens nein: Es gibt Probleme, die entschieden werden können, deren Komplexität jedoch nicht elementar ist. Das heißt, es gibt keinen Stapel der Form , der die Ausführungszeit eines Algorithmus für ein Problem der Größe n begrenzt.$2^{2^{2^{2^{\dots^n}}}}$

Ich hoffe, ich habe Ihre Frage richtig verstanden.

Dies ist eine etwas andere Sichtweise auf Ihre Frage als die von Marcus, aber angesichts Ihrer Erklärung, wie Sie zu dieser Frage gekommen sind, ist sie möglicherweise näher an dem, wonach Sie suchen.

Manchmal kann man beweisen, dass ein Problem entscheidbar ist, ohne in der Lage zu sein, den Algorithmus dafür aufzuzeigen. Das bekannteste Beispiel dafür ist die Arbeit von Robertson und Seymour über Graph-Minderjährige, die zeigt, dass jede erbliche Graph-Eigenschaft in polynomieller Zeit entschieden werden kann, indem nach einer geeigneten endlichen Liste verbotener Minderjähriger gesucht wird. Ihr Beweis zeigt nur, dass eine endliche Liste verbotener Minderjähriger existiert, liefert jedoch kein Rezept zum Auffinden der Liste.

Ich bin kein Experte auf diesem Gebiet, daher kenne ich kein konkretes Beispiel für eine erbliche Grapheneigenschaft, für die wir keinen Algorithmus darstellen können, da wir die Liste der verbotenen Minderjährigen nicht kennen und keine andere Möglichkeit dazu kennen das problem lösen, aber ich vermute, dass es solche beispiele gibt. (Und wir können die Laufzeit für die Suche nach einem Beispiel einschränken, wenn es existiert, da wir wissen, dass es höchstens 8 Milliarden Menschen auf der Welt gibt, und im schlimmsten Fall können wir sie alle fragen!)

$O(n^3)$$O(n^3)$

Um nur eine andere Perspektive hinzuzufügen, lassen Sie mich daran erinnern, dass nicht jedes Problem eine "intrinsische" Komplexität aufweist, die wahrscheinlich die interessanteste und irgendwie vernachlässigte Konsequenz von Blums Beschleunigungssatz ist.

Im Wesentlichen besagt der Satz, dass man, wenn man eine gewünschte Beschleunigung g festlegt, immer ein Rechenproblem P finden kann, das für jedes gilt Programm, das P löst, ein anderes Programm existiert, das P noch löst und g-mal schneller als das vorherige läuft.

Daher können Sie für diese Art von Problemen keine zeitliche Beschränkung festlegen. Erstaunliches und ziemlich rätselhaftes Ergebnis. Natürlich hat P eine sehr große Komplexität.

Den theoretischen Aspekt Ihrer Frage kümmert sich Markus. Praktisch gesehen ist eine interessante Art und Weise, Ihre Frage zu verstehen: Gibt es entscheidbare Probleme, für die wir keine Zeitgrenze kennen?

Die Antwort lautet: Ja, zum Beispiel kann es vorkommen, dass Sie einen Halbalgorithmus für JA-Instanzen Ihres Problems und einen Halbalgorithmus für NEIN-Instanzen haben. Dies gibt Ihnen Entscheidungsfreiheit für Ihr Problem, aber keine Zeitbeschränkung.

Hier ist ein allgemeines Beispiel: Nehmen Sie an, Sie haben ein axiomatisches System, mit dem Sie alle wahren Identitäten in einer Algebra beweisen können. Außerdem wissen Sie, dass falsche Identitäten immer von einer endlichen Struktur zeugen.

Dann haben Sie folgenden Algorithmus, um zu entscheiden, ob eine Identität vorliegt $I$ ist wahr: Zählen Sie parallel Beweise und endliche Strukturen auf und hören Sie auf, wenn Sie einen Beweis dafür finden $I$ oder eine Struktur, die das bezeugt $I$ist falsch. Es gibt Ihnen einen korrekten Algorithmus, aber keine Komplexitätsgrenze, es sei denn, Sie können die Größe von Beweisen und endlichen Strukturen in Bezug auf begrenzen$I$.

Ein Beispiel hierfür ist die affine lineare Logik (LLW): Es ist nun bekannt, dass sie turmvollständig ist [1], aber für einige Zeit waren keine Grenzen bekannt, und es wurde nur die Entscheidbarkeit gezeigt, wobei unter anderem endliche Modelleigenschaften verwendet wurden [2]. .

Verweise:

[1] Nicht-elementare Komplexität für die Verzweigung von VASS, MELL und Extensions. Ranko Lazic und Sylvain Schmitz. CSL-LICS 2014

[2] Die endliche Modelleigenschaft für verschiedene Fragmente der linearen Logik. Yves Lafont, J. Symb. Logik. 1997

Wie andere angegeben haben, wird die Frage nicht so gestellt, dass eine triviale Antwort vermieden wird. Es gibt jedoch einige verwandte / ähnliche Konzepte in der TCS- und Zahlentheorie.

1) in der Raum- und Zeithierarchie die Begriffe "zeitkonstruierbar" und "raumkonstruierbar" Funktionen benötigt. Nicht zeitkonstruierbare und nicht raumkonstruierbare Funktionen existieren und führen zu ungewöhnlichen Eigenschaften, die in den Blum-Theoremen zu finden sind, wie zum Beispiel den "Gap, Speedup" -Sätzen. Die meisten (alle?) Standardkomplexitätsklassen werden in Bezug auf räumlich und zeitlich konstruierbare Funktionen definiert.

2) Die Ackerman-Funktion ist vollständig rekursiv, aber nicht primitiv rekursiv, und dies hat Auswirkungen auf ihre Zeitbindung. Die primitiven rekursiven Funktionen repräsentieren in gewisser Weise die "grundlegenden" mathematischen Operationen.

3) Es gibt Thms über zahlentheoretische Sequenzen, die in der Peano-Arithmetik nicht berechenbar sind und so interpretiert werden können, dass sie nicht berechenbare Zeitgrenzen wie die Goodstein-Sequenz oder die Paris-Harrington- Thms erzeugen