Bounded arithmetic, proof complexity and two papers of Parikh

DOI10.1016/S0168-0072(98)00030-XMaRDI QIDQ1295443zbMATH OpenFDO

Authors Samuel R. Buss

Publication date 24 June 1999

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0168-0072(98)00030-X

zbMATH Keywords

bounded arithmeticcomplexity of proofsfeasibilityfeasible arithmeticsurvey

Mathematics Subject Classification ID

Structure of proofs (03F07) Complexity of proofs (03F20) First-order arithmetic and fragments (03F30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

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.

Recommendations

• scientific article; zbMATH DE number 1070621
• scientific article; zbMATH DE number 819737
• scientific article; zbMATH DE number 1344922
• Recent topics on bounded arithmetic and complexity theory
• The provably total search problems of bounded arithmetic
• scientific article; zbMATH DE number 2196511
• scientific article; zbMATH DE number 1670480
• On the provability logic of bounded arithmetic
• scientific article; zbMATH DE number 806753
• Fragments of bounded arithmetic and the lengths of proofs

Cites work

• A Machine-Oriented Logic Based on the Resolution Principle
• A note on a formalized arithmetic with function symbols ' and +
• A theorem on the formalized arithmetic with function symbols ' and +
• A unification algorithm for second-order monadic terms
• A unification-theoretic method for investigating the \(k\)-provability problem
• Context-free languages and rudimentary attributes
• Cuts, consistency statements and interpretations
• Cycling in proofs and feasibility
• Existence and feasibility in arithmetic
• scientific article; zbMATH DE number 440474 (Why is no real title available?)
• scientific article; zbMATH DE number 3912375 (Why is no real title available?)
• scientific article; zbMATH DE number 3950473 (Why is no real title available?)
• scientific article; zbMATH DE number 3974958 (Why is no real title available?)
• scientific article; zbMATH DE number 4039891 (Why is no real title available?)
• scientific article; zbMATH DE number 4066875 (Why is no real title available?)
• scientific article; zbMATH DE number 3708375 (Why is no real title available?)
• scientific article; zbMATH DE number 3758312 (Why is no real title available?)
• scientific article; zbMATH DE number 3786774 (Why is no real title available?)
• scientific article; zbMATH DE number 3557241 (Why is no real title available?)
• scientific article; zbMATH DE number 219032 (Why is no real title available?)
• scientific article; zbMATH DE number 3999883 (Why is no real title available?)
• scientific article; zbMATH DE number 819737 (Why is no real title available?)
• scientific article; zbMATH DE number 227056 (Why is no real title available?)
• scientific article; zbMATH DE number 3310055 (Why is no real title available?)
• scientific article; zbMATH DE number 3353257 (Why is no real title available?)
• scientific article; zbMATH DE number 3022401 (Why is no real title available?)
• Much shorter proofs: A bimodal investigation
• On Gödel's theorems on lengths of proofs I: Number of lines and speedup for arithmetics
• On the length of proofs in formal systems
• On the number of steps in proofs
• On the scheme of induction for bounded arithmetic formulas
• Proof schemata in Hilbert-type axiomatic theories
• Provable Fixed Points
• Provable fixed points in \(I \Delta{}_ 0+\Omega{}_ 1\)
• Rudimentary Predicates and Relative Computation
• Sets of theorems with short proofs
• Some Results on the Length of Proofs
• The bounded arithmetic hierarchy
• The number of proof lines and the size of proofs in first order logic
• The undecidability of k-provability
• The undecidability of the second-order unification problem
• Theory of Formal Systems. (AM-47)

Cited in

(8)

• Bounded arithmetic for NC, ALogTIME, L and NL
• Parikh and Wittgenstein
• scientific article; zbMATH DE number 4059392 (Why is no real title available?)
• The Complexity of Propositional Proofs
• scientific article; zbMATH DE number 2196511 (Why is no real title available?)
• Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
• Higher complexity search problems for bounded arithmetic and a formalized no-gap theorem
• The lengths of proofs: Kreisel's conjecture and Gödel's speed-up theorem

This page was built for publication: Bounded arithmetic, proof complexity and two papers of Parikh

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1295443)