Essential Structure of Proofs as a Measure of Complexity

Logica Universalis 14 (2):209-242 (2020)

Authors
Jaime Ramos
Universidad Nacional de Colombia
Abstract
The essential structure of proofs is proposed as the basis for a measure of complexity of formulas in FOL. The motivating idea was the recognition that distinct theorems can have the same derivation modulo some non essential details. Hence the difficulty in proving them is identical and so their complexity should be the same. We propose a notion of complexity of formulas capturing this property. With this purpose, we introduce the notions of schema calculus, schema derivation and description complexity of a schema formula. Based on these concepts we prove general robustness results that relate the complexity of introducing a logical constructor with the complexity of the component schema formulas as well as the complexity of a schema formula across different schema calculi.
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1007/s11787-020-00251-4
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Translate to english
Revision history

Download options

Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 49,066
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

On the Idea of a General Proof Theory.Dag Prawitz - 1974 - Synthese 27 (1-2):63 - 77.
Proof Complexity of Intuitionistic Implicational Formulas.Emil Jeřábek - 2017 - Annals of Pure and Applied Logic 168 (1):150-190.

View all 9 references / Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

Abstract Complexity Definition.Mariusz Stanowski - 2011 - Complicity: An International Journal of Complexity and Education (2).
The Depth of Resolution Proofs.Alasdair Urquhart - 2011 - Studia Logica 99 (1-3):349-364.
Is Complexity a Scientific Concept?Paul Taborsky - 2014 - Studies in History and Philosophy of Science Part A 47:51-59.
The Role of Quantifier Alternations in Cut Elimination.Philipp Gerhardy - 2005 - Notre Dame Journal of Formal Logic 46 (2):165-171.
Effective Complexity: In Which Sense is It Informative?Esteban Céspedes & Miguel Fuentes - forthcoming - Journal for General Philosophy of Science / Zeitschrift für Allgemeine Wissenschaftstheorie:1-16.
The Kolmogorov Complexity of Random Reals.Liang Yu, Decheng Ding & Rodney Downey - 2004 - Annals of Pure and Applied Logic 129 (1-3):163-180.
Complexity.J. Urry - 2006 - Theory, Culture and Society 23 (2-3):111-115.

Analytics

Added to PP index
2020-04-08

Total views
7 ( #953,112 of 2,311,214 )

Recent downloads (6 months)
7 ( #126,482 of 2,311,214 )

How can I increase my downloads?

Downloads

My notes

Sign in to use this feature