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 条

[1] On the proof complexity of logics of bounded branching
Jerabek, Emil
ANNALS OF PURE AND APPLIED LOGIC, 2023, 174 (01)
[2] CONSISTENCY PROOF OF A FRAGMENT OF PV WITH SUBSTITUTION IN BOUNDED ARITHMETIC
Yamagata, Yoriyuki
JOURNAL OF SYMBOLIC LOGIC, 2018, 83 (03) : 1063 - 1090
[3] Unprovability of Strong Complexity Lower Bounds in Bounded Arithmetic
Li, Jiatu
Oliveira, Igor C.
PROCEEDINGS OF THE 55TH ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING, STOC 2023, 2023, : 1051 - 1057
[4] Higher complexity search problems for bounded arithmetic and a formalized no-gap theorem
Thapen, Neil
ARCHIVE FOR MATHEMATICAL LOGIC, 2011, 50 (7-8): : 665 - 680
[5] Higher complexity search problems for bounded arithmetic and a formalized no-gap theorem
Neil Thapen
Archive for Mathematical Logic, 2011, 50 : 665 - 680
[6] MODELS OF BOUNDED ARITHMETIC THEORIES AND SOME RELATED COMPLEXITY QUESTIONS
Alam, Abolfazl
Moniri, Morteza
BULLETIN OF THE SECTION OF LOGIC, 2022, 51 (02): : 163 - 176
[7] Partial collapses of the Σ1 complexity hierarchy in models for fragments of bounded arithmetic
Adamowicz, Zofia
Kolodziejczyk, Leszek Aleksander
ANNALS OF PURE AND APPLIED LOGIC, 2007, 145 (01) : 91 - 95
[8] LOGICAL STRENGTH OF COMPLEXITY THEORY AND A FORMALIZATION OF THE PCP THEOREM IN BOUNDED ARITHMETIC
Pich, Jan
LOGICAL METHODS IN COMPUTER SCIENCE, 2015, 11 (02)
[9] A sorting network in bounded arithmetic
Jerabek, Emil
ANNALS OF PURE AND APPLIED LOGIC, 2011, 162 (04) : 341 - 355
[10] Partially definable forcing and bounded arithmetic
Albert Atserias
Moritz Müller
Archive for Mathematical Logic, 2015, 54 : 1 - 33

← 1 2 3 4 5 →