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

      0 references
      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
      [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

      Identifiers

      0 references
      0 references
      0 references
      0 references