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 条
  • [41] Proof Complexity and Textual Cohesion
    Dresner, Eli
    JOURNAL OF LOGIC LANGUAGE AND INFORMATION, 2015, 24 (01) : 53 - 64
  • [42] Proof Complexity of Modal Resolution
    Sarah Sigley
    Olaf Beyersdorff
    Journal of Automated Reasoning, 2022, 66 : 1 - 41
  • [43] Proof complexity of substructural logics
    Jalali, Raheleh
    ANNALS OF PURE AND APPLIED LOGIC, 2021, 172 (07)
  • [44] Separations in Proof Complexity and TFNP
    Goos, Mika
    Hollender, Alexandros
    Jain, Siddhartha
    Maystre, Gilbert
    Pires, William
    Robere, Robert
    Tao, Ran
    JOURNAL OF THE ACM, 2024, 71 (04)
  • [45] Proof Complexity and Textual Cohesion
    Eli Dresner
    Journal of Logic, Language and Information, 2015, 24 : 53 - 64
  • [46] Proof Complexity of Modal Resolution
    Sigley, Sarah
    Beyersdorff, Olaf
    JOURNAL OF AUTOMATED REASONING, 2022, 66 (01) : 1 - 41
  • [47] Hardness Amplification in Proof Complexity
    Beame, Paul
    Huynh, Trinh
    Pitassi, Toniann
    STOC 2010: PROCEEDINGS OF THE 2010 ACM SYMPOSIUM ON THEORY OF COMPUTING, 2010, : 87 - 96
  • [48] Proof Complexity Meets Algebra
    Atserias, Albert
    Ochremiak, Joanna
    ACM TRANSACTIONS ON COMPUTATIONAL LOGIC, 2019, 20 (01)
  • [49] Circuit Complexity, Proof Complexity and Polynomial Identity Testing
    Grochow, Joshua A.
    Pitassi, Toniann
    2014 55TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2014), 2014, : 110 - 119
  • [50] An independence result on weak second order bounded arithmetic
    Kuroda, S
    MATHEMATICAL LOGIC QUARTERLY, 2001, 47 (02) : 183 - 186
12345