RELATING THE BOUNDED ARITHMETIC AND POLYNOMIAL-TIME HIERARCHIES

被引：29

作者：

BUSS, SR

机构：

[1] Department of Mathematics, University of California, San Diego, La Jolla

来源：

ANNALS OF PURE AND APPLIED LOGIC | 1995年 / 75卷 / 1-2期

基金：

美国国家科学基金会;

关键词：

D O I：

10.1016/0168-0072(94)00057-A

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

The bounded arithmetic theory S-2 is finitely axiomatized if and only if the polynomial hierarchy provably collapses. If T-2(i) equals S-2(i+1) then T-2(i) is equal to S-2 and proves that the polynomial time hierarchy collapses to Sigma(i+3)(p), and, in fact, to the Boolean hierarchy over Sigma(i+2)(p) and to Sigma(i+1)(p)/poly.

引用

页码：67 / 77

页数：11

共 14 条

[1]

Buss S. R., 1985, THESIS PRINCETON U

[2] AN APPLICATION OF BOOLEAN COMPLEXITY TO SEPARATION PROBLEMS IN BOUNDED ARITHMETIC [J].

BUSS, SR ;

KRAJICEK, J .

PROCEEDINGS OF THE LONDON MATHEMATICAL SOCIETY, 1994, 69 :1-21

[3]

BUSS SR, 1990, CONT MATH, V106

[4]

BUSS SR, 1994, 9TH P INT C LOG METH, P29

[5]

CHANG R, 1990, 5TH P STRUCT COMPL T, P169

[6]

Karp R.M., 1982, ENSEIGN MATH, V28, P191

[7] FRAGMENTS OF BOUNDED ARITHMETIC AND BOUNDED QUERY CLASSES [J].

KRAJICEK, J .

TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 1993, 338 (02) :587-598

[8] BOUNDED ARITHMETIC AND THE POLYNOMIAL HIERARCHY [J].

KRAJICEK, J ;

PUDLAK, P ;

TAKEUTI, G .

ANNALS OF PURE AND APPLIED LOGIC, 1991, 52 (1-2) :143-153

[9]

KRAJICEK J, 1992, MATH SCI RES I PUBLI, V21, P287

[10]

PUDLAK P, 1992, MATH SCI RES I PUBLI, V21, P499

← 1 2 →