×

Arithmetic theories for computational complexity problems. (English) Zbl 0611.03018

Ein Ansatz zum genaueren Verständnis der Hierarchie von Komplexitätsklassen besteht darin, eine ”Übersetzung” der komplexitätstheoretischen Probleme in entsprechende logische Probleme zu finden.
Die Autoren verallgemeinern eine solche Konstruktion von R. A. DeMillo und R. J. Lipton (1979) und geben eine Reihe von Anwendungen an. Einige davon korrespondieren mit der polynomial time-Hierarchie von L. J. Stockmeyer (1976).
Reviewer: E.Heinrich

MSC:

03D15 Complexity of computation (including implicit computational complexity)
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI