Schwellenfragen auf Endlichkeitsfragen reduzieren

In der Regel ist es einfacher, über die Berechnung zu urteilen, wenn die Begrenzung in der Endlichkeit der Berechnung besteht, als über einen Schwellenwert wie "in polynomieller Zeit berechenbar".

In der formalen Sprachtheorie zum Beispiel lieber das $\exists n. x^{n+1} = x^n$ Um aperiodische Monoide zu charakterisieren, ist es einfacher, profinite Wörter zu verwenden, so dass $x^{\omega+1} = x^{\omega}$ .

In der Komplexitätstheorie ist die einzige mir bekannte Technik, die damit verbunden ist, der Auffülltrick, zum Beispiel das Problem von P vs NP mit EXPTIME vs NEXPTIME zu verbinden. Aber das natürliche unendliche Äquivalent von Komplexitätsfragen wären Berechenbarkeitsfragen.

Gibt es einige Ergebnisse, die Komplexität mit Fragen zur Berechenbarkeit verknüpfen, indem sie eine Codierung verwenden, so dass die Ressourcenschwelle der Komplexitätstheorie zu einer Endlichkeitsfrage der Berechnung in der Berechenbarkeitstheorie wird?

Sipser hat bewiesen, dass keine unendliche Parität durch eine (unendliche) Schaltung mit konstanter Tiefe berechnet werden kann, die Sie als Aufwärmphase ansehen können, bis das Ergebnis lautet, dass PARITÄT nicht in .$AC^0$

Es gibt auch einige Ergebnisse und Versuche, die untere Schranke der Beweiskomplexität unter Verwendung von Nichtstandardmodellen zu beweisen (einige Ergebnisse von Ajtai und Krajicek. Siehe insbesondere Krajiceks "Forcen mit Zufallsvariablen und Beweiskomplexität", erhältlich von Cambridge Press, aber auch einen Entwurf online verfügbar ). Die Grundidee besteht darin, ein Nichtstandardmodell der Arithmetik zu erstellen, in dem eine Aussage im Modell falsch ist (und nicht "wahr, aber ohne kurze Beweise"), und dann aus den Eigenschaften des Modells auf eine entsprechende endliche Folge zu schließen Anweisungen haben in einigen Beweissystemen keine polynomischen Beweise.

Ich bin mir nicht sicher, aber ich habe den Eindruck, dass diese Ergebnisse häufig sozusagen "die Asymptoten unter der Haube verstecken", dass es sich nicht so sehr um eine Verringerung von der Schwelle zur Endlichkeit handelt, sondern vielmehr um eine neue mathematische Sprache, in der "falsch" in der Neue Sprache entspricht "ohne kurze Beweise" in der alten Sprache. Das heißt nicht, dass die neue Sprache keinen nützlichen neuen Standpunkt bietet, aber ich bin mir nicht ganz sicher, ob es das ist, wonach Sie suchen.

$P$$NP$

Es handelt sich also nicht per se um eine unendliche Berechnung, sondern um die Ausdruckbarkeit des Problems in einem gegebenen Modell. Es ist jedoch in dem Sinne eng, dass es ein quantitatives Problem in ein qualitatives verwandelt.