On the computational complexity of cut-reduction
Annals of Pure and Applied Logic 161 (6):711-736 (2010)
Abstract
Using appropriate notation systems for proofs, cut-reduction can often be rendered feasible on these notations. Explicit bounds can be given. Developing a suitable notation system for Bounded Arithmetic, and applying these bounds, all the known results on definable functions of certain such theories can be reobtained in a uniform wayDOI
10.1016/j.apal.2009.06.004
Links
PhilArchive
External links
(no proxy)
Setup an account with your affiliations in order to access resources via your University's proxy server
Through your library
- Sign in / register and customize your OpenURL resolver
- Configure custom resolver
My notes
Similar books and articles
Deterministic chaos and computational complexity: The case of methodological complexity reductions. [REVIEW]Theodor Leiber - 1999 - Journal for General Philosophy of Science / Zeitschrift für Allgemeine Wissenschaftstheorie 30 (1):87-101.
Computation models for parameterized complexity.Marco Cesati & Miriam Dilanni - 1997 - Mathematical Logic Quarterly 43 (2):179-202.
Computational complexity on computable metric spaces.Klaus Weirauch - 2003 - Mathematical Logic Quarterly 49 (1):3-21.
Strong isomorphism reductions in complexity theory.Sam Buss, Yijia Chen, Jörg Flum, Sy-David Friedman & Moritz Müller - 2011 - Journal of Symbolic Logic 76 (4):1381-1402.
The Computational Complexity of Quantified Reciprocals.Jakub Szymanik - 2009 - In Peter Bosch, David Gabelaia & Jérôme Lang (eds.), Lecture Notes on Artificial Intelligence 5422, Logic, Language, and Computation 7th International Tbilisi Symposium on Logic, Language, and Computation. Springer.
Computational complexity reduction and interpretability improvement of distance-based decision trees.Marcin Blachnik & Mirosław Kordos - 2012 - In Emilio Corchado, Vaclav Snasel, Ajith Abraham, Michał Woźniak, Manuel Grana & Sung-Bae Cho (eds.), Hybrid Artificial Intelligent Systems. Springer. pp. 288--297.
Computational Complexity and Godel's Incompleteness Theorem.Gregory J. Chaitin - 1970 - [Rio De Janeiro, Centro Técnico Científico, Pontifícia Universidade Católica Do Rio De Janeiro.
Hybrid Elections Broaden Complexity‐Theoretic Resistance to Control.Edith Hemaspaandra, Lane A. Hemaspaandra & Jörg Rothe - 2009 - Mathematical Logic Quarterly 55 (4):397-424.
Computational complexity of some Ramsey quantifiers in finite models.Marcin Mostowski & Jakub Szymanik - 2007 - Bulletin of Symbolic Logic 13:281--282.
Computational complexity analysis can help, but first we need a theory.Todd Wareham, Iris van Rooij & Moritz Müller - 2008 - Behavioral and Brain Sciences 31 (4):399-400.
Computational Complexity of Polyadic Lifts of Generalized Quantifiers in Natural Language.Jakub Szymanik - 2010 - Linguistics and Philosophy 33 (3):215-250.
Analytics
Added to PP
2013-12-18
Downloads
49 (#241,668)
6 months
1 (#454,876)
2013-12-18
Downloads
49 (#241,668)
6 months
1 (#454,876)
Historical graph of downloads
Citations of this work
Polynomial local search in the polynomial hierarchy and witnessing in fragments of bounded arithmetic.Arnold Beckmann & Samuel R. Buss - 2009 - Journal of Mathematical Logic 9 (1):103-138.
References found in this work
Über eine bisher noch nicht benützte erweiterung Des finiten standpunktes.Von Kurt Gödel - 1958 - Dialectica 12 (3‐4):280-287.
Notation systems for infinitary derivations.Wilfried Buchholz - 1991 - Archive for Mathematical Logic 30 (5-6):277-296.
Structure and definability in general bounded arithmetic theories.Chris Pollett - 1999 - Annals of Pure and Applied Logic 100 (1-3):189-245.
Exact Bounds for lengths of reductions in typed λ-calculus.Arnold Beckmann - 2001 - Journal of Symbolic Logic 66 (3):1277-1285.
