Complete problems in the first-order predicate calculus (Q1075318)

Neben den klassischen Komplexitätsklassen P und NP wird seit längerem eine Reihe weiterer solcher Klassen untersucht. Der Autor stellt einen Zusammenhang zwischen einigen Formeln der Prädikatenlogik 1. Stufe und Turingmaschinen her. Diese zunächst sehr abstrakte Aussage wird dazu benutzt, eine natürliche Hierarchie vollständiger Probleme für die Klassen P, NP, PSPACE, deterministische und nichtdeterministische exponentielle Zeit, deterministische und nichtdeterministische doppelt exponentielle Zeit, DLOGSPACE und NLOGSPACE zu entwickeln. Eine ähnliche Hierarchie ergibt sich, wenn nach der Existenz von Beweisen einer vorgegebenen maximalen Tiefe für die oben genannten Formeln gefragt wird. Spezielle Resultate betreffen u.a. ein erstes Beispiel eines vollständigen Problems für EXPSPACE. Eine mögliche Anwendung dieser Ergebnisse liegt in der Beschleunigung von Beweisführungsprogrammen.