Applicative theories for the polynomial hierarchy of time and its levels

DOI10.1016/J.APAL.2012.05.006zbMath1275.03131OpenAlexW2042217238MaRDI QIDQ1946672

Reinhard Kahle, Isabel Oitavem

Publication date: 15 April 2013

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.apal.2012.05.006

zbMATH Keywords

computational complexityapplicative theoriesinduction schemeslevels of the polynomial hierarchypolynomial hierarchy of time

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) First-order arithmetic and fragments (03F30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Hierarchies of computability and definability (03D55)

Related Items (3)

Implicit recursion-theoretic characterizations of counting classes ⋮ “Sehr geehrter Herr Professor!” Proof Theory in 1949 in a Letter from Schütte to Bernays ⋮ Applicative theories for logarithmic complexity classes

This page was built for publication: Applicative theories for the polynomial hierarchy of time and its levels