Essential structure of proofs as a measure of complexity (Q2183713)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Essential structure of proofs as a measure of complexity
scientific article

    Statements

    Essential structure of proofs as a measure of complexity (English)
    0 references
    0 references
    0 references
    0 references
    27 May 2020
    0 references
    The article is well organized and written. Mainly, it shows that introducing the notions of \textit{schema calculus, schema derivation} and \textit{description complexity of a schema formula}, they were able to recognize that two distinct derivations of two distinct theorems can be the same in the sense that both are instances of the same schema derivation, so, intuitively both must have the same description complexity in an appropriate schema calculus. Besides, using these concepts they prove general robustness results relating to description complexity of a schema formula across Hilbert and Gentzen calculus. In page 212, inside the definition of \textit{schema calculus}, subpart \textit{proviso oracle map}, it will be appropriate to explicitly mention that \(\Lambda \subseteq A\).
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    description complexity
    0 references
    schema calculus
    0 references
    schema derivation
    0 references
    uniform and non-uniform robustness
    0 references
    0 references
    0 references