Uniform normal form for general time-bounded complexity classes (Q1087539)

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 haben in einer früheren Arbeit ein arithmetisches Formelschema zur Charakterisierung von NP angegeben und insbesondere (durch die Angabe von Schranken für die Anzahl der Quantorenwechsel im Präfix) eine ''Normalform'' solcher Ausdrücke. Die vorliegende Arbeit vereinfacht diese Normalform und diskutiert ein ähnliches Ergebnis von S. Jukna (1982).