1991•Journal of Symbolic LogicRequires access

A second order version of S2i and U21

Gaisi Takeuti

Open publisher page 5 citations

Abstract

In [1] S. Buss introduced systems of bounded arithmetic , , , (i = 1, 2, 3, …). and are first order systems and and are second order systems. and are closely related to and respectively in the polynomial hierarchy, and and are closely related to PSPACE and EXPTIME respectively. One of the most important problems in bounded arithmetic is whether the hierarchy of bounded arithmetic collapses, i.e. whether = or = for some i, or whether = , or whether is a conservative extension of S2 = ⋃i . These problems are relevant to the problems whether the polynomial hierarchy PH collapses or whether PSPACE = PH or whether PSPACE = EXPTIME. It was shown in [4] that = implies and consequently the collapse of the polynomial hierarchy. We believe that the separation problems of bounded arithmetic and the separation problems of computational complexities are essentially the same problem, and the solution of one of them will lead to the solution of the other.

About this research paper

What this paper is about

In [1] S. Buss introduced systems of bounded arithmetic , , , (i = 1, 2, 3, …). and are first order systems and and are second order systems. and are closely related to and respectively in the polynomial hierarchy, and and are closely related to PSPACE and EXPTIME respectively. One of the most important problems in bounded arithmetic is whether the hierarchy of bounded arithmetic collapses, i.e. whether = or = for some i, or whether = , or whether is a conservative extension of S2 = ⋃i . These problems are relevant to the problems whether the polynomial hierarchy PH collapses or whether PSPACE = PH or whether PSPACE = EXPTIME. It was shown in [4] that = implies and consequently the collapse of the polynomial hierarchy. We believe that the separation problems of bounded arithmetic and the separation problems of computational complexities are essentially the same problem, and the solution of one of them will lead to the solution of the other.

Why it matters

OpenAlex reports 5 citations for this work. Citation counts describe recorded attention and do not establish research quality.

Key contribution

A contribution statement is not available in the OpenAlex record.

Method / approach

Method details are not available in the OpenAlex metadata.

Main findings

Findings are not separately available in the OpenAlex metadata.

Limitations

Limitations are not available in the OpenAlex metadata.

Applications

Application details are not available in the OpenAlex metadata.

Available abstract

In [1] S. Buss introduced systems of bounded arithmetic , , , (i = 1, 2, 3, …). and are first order systems and and are second order systems. and are closely related to and respectively in the polynomial hierarchy, and and are closely related to PSPACE and EXPTIME respectively. One of the most important problems in bounded arithmetic is whether the hierarchy of bounded arithmetic collapses, i.e. whether = or = for some i, or whether = , or whether is a conservative extension of S2 = ⋃i . These problems are relevant to the problems whether the polynomial hierarchy PH collapses or whether PSPACE = PH or whether PSPACE = EXPTIME. It was shown in [4] that = implies and consequently the collapse of the polynomial hierarchy. We believe that the separation problems of bounded arithmetic and the separation problems of computational complexities are essentially the same problem, and the solution of one of them will lead to the solution of the other.

Key concepts: PSPACE, Polynomial hierarchy, Bounded function, Hierarchy, Mathematics, EXPTIME, Polynomial, Combinatorics

Related papers

Back to paper searchBrowse research topicsOriginal source
A second order version of S2i and U21 — Research Paper | ScholarLens