Bounded arithmetic, proof complexity and two papers of Parikh

被引：2

作者：

Buss, SR ^{[1
]}

机构：

[1] Univ Calif San Diego, Dept Math, La Jolla, CA 92093 USA

来源：

ANNALS OF PURE AND APPLIED LOGIC | 1999年 / 96卷 / 1-3期

基金：

美国国家科学基金会;

关键词：

feasibility; exponentiation; bounded arithmetic; proof length; proof complexity; unification;

D O I：

10.1016/S0168-0072(98)00030-X

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

This article surveys R. Parikh's work on feasibility, bounded arithmetic and the complexity of proofs. We discuss in depth two of Parikh's papers on these subjects and some of the subsequent progress in the areas of feasible arithmetic and lengths of proofs. (C) 1999 Elsevier Science B.V. All rights reserved.

引用

页码：43 / 55

页数：13

共 50 条

[31] Third-order computation and bounded arithmetic
Skelley, Alan
JOURNAL OF LOGIC AND COMPUTATION, 2007, 17 (06) : 1167 - 1191
[32] Cuts and overspill properties in models of bounded arithmetic
Moniri, Morteza
Sajjadi, S. Hosein
IRANIAN JOURNAL OF MATHEMATICAL SCIENCES AND INFORMATICS, 2013, 8 (01): : 59 - 66
[33] Structure and definability in general bounded arithmetic theories
Pollett, C
ANNALS OF PURE AND APPLIED LOGIC, 1999, 100 (1-3) : 189 - 245
[34] An unexpected separation result in Linearly Bounded Arithmetic
Beckmann, A
Johannsen, J
MATHEMATICAL LOGIC QUARTERLY, 2005, 51 (02) : 191 - 200
[35] On theories of bounded arithmetic for NC1
Jerabek, Emil
ANNALS OF PURE AND APPLIED LOGIC, 2011, 162 (04) : 322 - 340
[36] A remark on independence results for sharply bounded arithmetic
Johannsen, J
MATHEMATICAL LOGIC QUARTERLY, 1998, 44 (04) : 568 - 570
[37] ON PROVING CONSISTENCY OF EQUATIONAL THEORIES IN BOUNDED ARITHMETIC
Beckmann, Arnold
Yamagata, Yoriyuki
JOURNAL OF SYMBOLIC LOGIC, 2025,
[38] Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic
Ilango, Rahul
Li, Jiatu
Williams, R. Ryan
PROCEEDINGS OF THE 55TH ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING, STOC 2023, 2023, : 1076 - 1089
[39] End extensions of models of linearly bounded arithmetic
Zambella, D
ANNALS OF PURE AND APPLIED LOGIC, 1997, 88 (2-3) : 263 - 277
[40] Upper and lower Ramsey bounds in bounded arithmetic
Ojakian, K
ANNALS OF PURE AND APPLIED LOGIC, 2005, 135 (1-3) : 135 - 150

← 1 2 3 4 5 →