Bounded arithmetic, proof complexity and two papers of Parikh

DOI10.1016/S0168-0072(98)00030-XzbMath0924.03106MaRDI QIDQ1295443

Samuel R. Buss

Publication date: 24 June 1999

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

zbMATH Keywords

surveybounded arithmeticfeasibilitycomplexity of proofsfeasible arithmetic

Mathematics Subject Classification ID

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

Related Items (3)

The lengths of proofs: Kreisel's conjecture and Gödel's speed-up theorem ⋮ Parikh and Wittgenstein ⋮ The Complexity of Propositional Proofs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The number of proof lines and the size of proofs in first order logic
• On the scheme of induction for bounded arithmetic formulas
• A unification algorithm for second-order monadic terms
• On the number of steps in proofs
• The undecidability of the second-order unification problem
• On the length of proofs in formal systems
• The undecidability of \(k\)-provability
• Provable fixed points in \(I \Delta{}_ 0+\Omega{}_ 1\)
• A theorem on the formalized arithmetic with function symbols ' and +
• A note on a formalized arithmetic with function symbols ' and +
• A unification-theoretic method for investigating the \(k\)-provability problem
• Proof schemata in Hilbert-type axiomatic theories
• Theory of Formal Systems. (AM-47)
• Much shorter proofs: A bimodal investigation
• Cuts, consistency statements and interpretations
• Provable Fixed Points
• Sets of theorems with short proofs
• The bounded arithmetic hierarchy
• Rudimentary Predicates and Relative Computation
• On Gödel's theorems on lengths of proofs I: Number of lines and speedup for arithmetics
• Cycling in proofs and feasibility
• A Machine-Oriented Logic Based on the Resolution Principle
• Context-free languages and rudimentary attributes
• Existence and feasibility in arithmetic
• Some Results on the Length of Proofs

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