Bounded arithmetic, proof complexity and two papers of Parikh
type: Item
instance of: scholarly article
title: Bounded arithmetic, proof complexity and two papers of Parikh
zbMATH Open document ID: 0924.03106
DOI: 10.1016/S0168-0072(98)00030-X
author: Samuel R. Buss
published in: Annals of Pure and Applied Logic
publication date: 1999-06-24T00:00:00Z
review text: This article surveys R. Parikh's work on feasibility, bounded arithmetic and the complexity of proofs. The author discusses 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.
Mathematics Subject Classification ID: 03F30
Mathematics Subject Classification ID: 03F20
Mathematics Subject Classification ID: 03F07
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 1308114
zbMATH Keywords: survey
zbMATH Keywords: feasibility
zbMATH Keywords: bounded arithmetic
zbMATH Keywords: complexity of proofs
zbMATH Keywords: feasible arithmetic
reviewed by: M.Tetruashvili
MaRDI profile type: Publication
cites work: Q3140631
cites work: Q3800030
cites work: The undecidability of \(k\)-provability
cites work: On Gödel's theorems on lengths of proofs I: Number of lines and speedup for arithmetics
cites work: Provable fixed points in \(I \Delta{}_ 0+\Omega{}_ 1\)
cites work: Cycling in proofs and feasibility
cites work: Much shorter proofs: A bimodal investigation
cites work: Q4133141
cites work: Provable Fixed Points
cites work: Q3741624
cites work: A unification algorithm for second-order monadic terms
cites work: A unification-theoretic method for investigating the \(k\)-provability problem
cites work: Q5760848
cites work: The undecidability of the second-order unification problem
cites work: Q5286672
cites work: The bounded arithmetic hierarchy
cites work: Context-free languages and rudimentary attributes
cites work: On the number of steps in proofs
cites work: Q4856172
cites work: The number of proof lines and the size of proofs in first order logic
cites work: Q3964563
cites work: On the length of proofs in formal systems
cites work: Q4726219
cites work: Q5628106
cites work: Q3778747
cites work: Proof schemata in Hilbert-type axiomatic theories
cites work: Existence and feasibility in arithmetic
cites work: Some Results on the Length of Proofs
cites work: Q3720554
cites work: Q3689182
cites work: Cuts, consistency statements and interpretations
cites work: Sets of theorems with short proofs
cites work: A Machine-Oriented Logic Based on the Resolution Principle
cites work: Q3900044
cites work: Q4694581
cites work: Theory of Formal Systems. (AM-47)
cites work: Q3941393
cites work: On the scheme of induction for bounded arithmetic formulas
cites work: Rudimentary Predicates and Relative Computation
cites work: Q5590784
cites work: A theorem on the formalized arithmetic with function symbols ' and +
cites work: A note on a formalized arithmetic with function symbols ' and +
Recommended article: Q4357061
Recommended article: Q4856172
Recommended article: Q4266170
Recommended article: Q3087409
Recommended article: The provably total search problems of bounded arithmetic
Recommended article: Q5465358
Recommended article: Q2753676
Recommended article: On the provability logic of bounded arithmetic
Recommended article: Q4850554
Recommended article: Fragments of bounded arithmetic and the lengths of proofs
description: scientific article; zbMATH DE number 1308114