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 条

[21] A bounded arithmetic AID for Frege systems
Arai, T
ANNALS OF PURE AND APPLIED LOGIC, 2000, 103 (1-3) : 155 - 199
[22] Lifting independence results in bounded arithmetic
Mario Chiari
Jan Krajíček
Archive for Mathematical Logic, 1999, 38 : 123 - 138
[23] Lifting independence results in bounded arithmetic
Chiari, M
Krajicek, J
ARCHIVE FOR MATHEMATICAL LOGIC, 1999, 38 (02) : 123 - 138
[24] Structures interpretable in models of bounded arithmetic
Thapen, N
ANNALS OF PURE AND APPLIED LOGIC, 2005, 136 (03) : 247 - 266
[25] APPROXIMATE COUNTING BY HASHING IN BOUNDED ARITHMETIC
Jerabek, Emil
JOURNAL OF SYMBOLIC LOGIC, 2009, 74 (03) : 829 - 860
[26] Sprague–Grundy theory in bounded arithmetic
Satoru Kuroda
Archive for Mathematical Logic, 2022, 61 : 233 - 262
[27] Uniform proof complexity
Beckmann, A
JOURNAL OF LOGIC AND COMPUTATION, 2005, 15 (04) : 433 - 446
[28] POLYNOMIAL LOCAL SEARCH IN THE POLYNOMIAL HIERARCHY AND WITNESSING IN FRAGMENTS OF BOUNDED ARITHMETIC
Beckmann, Arnold
Buss, Samuel R.
JOURNAL OF MATHEMATICAL LOGIC, 2009, 9 (01) : 103 - 138
[29] On rules and parameter free systems in bounded arithmetic
Cordon-Franco, A.
Fernandez-Margarit, A.
Lara-Martin, F. F.
COMPUTATION AND LOGIC IN THE REAL WORLD, PROCEEDINGS, 2007, 4497 : 179 - +
[30] Sprague-Grundy theory in bounded arithmetic
Kuroda, Satoru
ARCHIVE FOR MATHEMATICAL LOGIC, 2022, 61 (1-2) : 233 - 262

← 1 2 3 4 5 →