Notes on polynomially bounded arithmetic

被引：72

作者：

Zambella, D

机构：

[1] Dept. of Math. and Computer Science, University of Amsterdam, 1018 Tv Amsterdam

来源：

JOURNAL OF SYMBOLIC LOGIC | 1996年 / 61卷 / 03期

关键词：

D O I：

10.2307/2275794

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We characterize the collapse of Buss' bounded arithmetic in terms or the provable collapse of the polynomial time hierarchy. we include also some general model-theoretical investigations on fragments of hounded arithmetic.

引用

页码：942 / 966

页数：25

共 16 条

[1]

ATTAI M, 1988, IEEE, P346

[2]

ATTAI M, 1983, ANN PURE APPL LOGIC, V24, P1

[3]

BUSS S, 1986, BOUNDED ARITHMETIC

[4]

BUSS SR, 1987, CONT MATH, V106, P57

[5]

BUSS SR, IN PRESS RELATING BO

[6]

COBHAM A, 1986, LECT NOTES COMPUTATI, V221, P125

[7]

HAJEK P, 1993, METAMATHEMATICS 1 OR

[8]

Kadin J., 1988, Proceedings: Structure in Complexity Theory Third Annual Conference (Cat. No.88CH2542-9), P278, DOI 10.1109/SCT.1988.5287

[9] EXPONENTIATION AND 2ND-ORDER BOUNDED ARITHMETIC [J].

KRAJICEK, J .

ANNALS OF PURE AND APPLIED LOGIC, 1990, 48 (03) :261-276

[10] 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

← 1 2 →