Bounded arithmetic, proof complexity and two papers of Parikh (Q1295443): Difference between revisions

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.

0 references

zbMATH Keywords

survey

0 references

feasibility

0 references

bounded arithmetic

0 references

complexity of proofs

0 references

feasible arithmetic

0 references

reviewed by

M.Tetruashvili

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

Q3140631

0 references

Q3800030

0 references

The undecidability of \(k\)-provability

0 references

On Gödel's theorems on lengths of proofs I: Number of lines and speedup for arithmetics

0 references

Provable fixed points in \(I \Delta{}_ 0+\Omega{}_ 1\)

0 references

Cycling in proofs and feasibility

0 references

Much shorter proofs: A bimodal investigation

0 references

Q4133141

0 references

Provable Fixed Points

0 references

Q3741624

0 references

A unification algorithm for second-order monadic terms

0 references

A unification-theoretic method for investigating the \(k\)-provability problem

0 references

Q5760848

0 references

The undecidability of the second-order unification problem

0 references

Q5286672

0 references

The bounded arithmetic hierarchy

0 references

Context-free languages and rudimentary attributes

0 references

On the number of steps in proofs

0 references

Q4856172

0 references

The number of proof lines and the size of proofs in first order logic

0 references

Q3964563

0 references

On the length of proofs in formal systems

0 references

Q4726219

0 references

Q5628106

0 references

Q3778747

0 references

Proof schemata in Hilbert-type axiomatic theories

0 references

Existence and feasibility in arithmetic

0 references

Some Results on the Length of Proofs

0 references

Q3720554

0 references

Q3689182

0 references

Cuts, consistency statements and interpretations

0 references

Sets of theorems with short proofs

0 references

A Machine-Oriented Logic Based on the Resolution Principle

0 references

Q3900044

0 references

Q4694581

0 references

Theory of Formal Systems. (AM-47)

0 references

Q3941393

0 references

On the scheme of induction for bounded arithmetic formulas

0 references

Rudimentary Predicates and Relative Computation

0 references

Q5590784

0 references

A theorem on the formalized arithmetic with function symbols ' and +

0 references

A note on a formalized arithmetic with function symbols ' and +

0 references

Identifiers

zbMATH Open document ID

0924.03106

0 references

DOI

10.1016/S0168-0072(98)00030-X

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:1295443

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