Bounded arithmetic, proof complexity and two papers of Parikh
From MaRDI portal
Publication:1295443
DOI10.1016/S0168-0072(98)00030-XzbMath0924.03106MaRDI QIDQ1295443
Publication date: 24 June 1999
Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)
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
The lengths of proofs: Kreisel's conjecture and Gödel's speed-up theorem, Parikh and Wittgenstein, The Complexity of Propositional Proofs
Cites Work
- 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
- 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
