Homer, Steve; Reif, John Arithmetic theories for computational complexity problems. (English) Zbl 0611.03018 Inf. Control 69, 1-11 (1986). 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 Cited in 1 Document MSC: 03D15 Complexity of computation (including implicit computational complexity) 68Q25 Analysis of algorithms and problem complexity Keywords:polynomial time hierarchy PDFBibTeX XMLCite \textit{S. Homer} and \textit{J. Reif}, Inf. Control 69, 1--11 (1986; Zbl 0611.03018) Full Text: DOI