Summary
We investigate the second order bounded arithmetical systems which is isomorphic to TACi, TNCi or TLS.
Similar content being viewed by others
References
Allen B.: Arithmetizing uniform NC. Ann. Pure Appl. Logic53, 1–50 (1991)
Buss S.: Bounded arithmetic. Napoli: Biblopolis 1986
Clote P., Takeuti G.: Bounded arithmetic for NC, ALOGTIME, L and NL. Ann. Pure Appl. Logic56, 73–117 (1992)
Colte P., Takeuti G.: First order bounded arithmetic and small boolean circuit complexity classes (to appear)
Håstad J.: Computational limitations of small-depth circuits. Cambridge, Massachusetts: MIT Press 1987
Hájek P., Pudlák P.: Metamathematics of first-order arithmetic. Berlin Heidelberg New York: Springer 1991
Krajíček J., Takeuti G.: On boundedΣ 11 polynomial induction. In: Buss S., Scott P. (eds.) Feasible mathematics, pp. 259–280. Basel: Birkhäuser 1990
Takeuti G.: Proof theory, 2nd ed. Amsterdam: North-Holland
Takeuti G.:S i3 and0V i(BD)2 . Arch. Math. Logic29, 149–169 (1990)
Takeuti G.: RSUV Isomorphisms. In: Clote P., Krajíček J. (eds.) Arithmetic, proof theory and computational complexity, pp. 364–386. Oxford: Oxford Univ. Press 1993
Wilkie A.J., Paris J.B.: On the scheme of induction for bounded arithmetical formulas. Ann. Pure Appl. Logic35, 261–302 (1987)
Yao A.: Separating the polynomial-time hierachy by oracles. Proceedings 26th Annual IEEE Symposium on Foundations of Computer Science, pp. 1–10 (1985)
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Takeuti, G. RSUV isomorphisms for TACi, TNCi and TLS. Arch Math Logic 33, 427–453 (1995). https://doi.org/10.1007/BF02390458
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF02390458