No label defined (Q3755452)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4004177
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 4004177 |
Statements
1986
0 references
contradiction
0 references
relativization
0 references
complexity
0 references
proof theory
0 references
upper bound
0 references
finitistic point of view
0 references
polynomial time
0 references
rates of growth
0 references
0.8261159062385559
0 references
0.81211256980896
0 references
0.8082732558250427
0 references
[For the entire collection see Zbl 0587.00004.] For a formal theory T, let \(Con_ T(n)\) be a reasonable formulation of the idea ''there is not proof of a contradiction in T whose length is bounded by n. The main results of the paper are as follows. For reasonable T extending Robinson's arithmetic Q, the minimum length of a proof of \(Con_ T(n)\) in T is bounded below and above by functions of the form \(n^{\epsilon}\) \((\epsilon >0)\) and \(n^ k\), respectively. Here the length of a proof is measured by the total number of symbols in the proof. A corollary on the result on the lower bound is that Gödel- Bernays set theory provides a more than elementary speedup of a certain family of proofs in Zermelo-Fraenkel set theory. The paper represents a contribution to the project of relativizing various results of proof theory to 'feasible' (polynomial time) functions. A basic step in this project is the relativization of the notion of the numeralwize representability of a relation. The notion NP from complexity theory provides an aid in accomplishing this step. Thus we see the influence of computer science on proof theory. The author hopes that there might also be an influence in the other direction. Namely, he mentions a couple of problems which, if answered positively, would extend his upper bound results; but a negative answer to either problem would imply NP\(\neq coNP\) (hence also \(P\neq NP).\) The author sees the project, above, as contributing to the development of proof theory from the finitistic point of view. The word 'finitistic' is interpreted as meaning (at least) that all functions should be computable in polynomial time. Might there be some interesting relations between results on rates of growth, of the kind obtained in the present paper, and the results on the ordinal lengths of proofs, of the sort obtained by Schütte's school of proof theory?
0 references