The proof complexity of linear algebra

&
Annals of Pure and Applied Logic 130 (1-3):277-323 (2004)
  Copy   BIBTEX

Abstract

We introduce three formal theories of increasing strength for linear algebra in order to study the complexity of the concepts needed to prove the basic theorems of the subject. We give what is apparently the first feasible proofs of the Cayley–Hamilton theorem and other properties of the determinant, and study the propositional proof complexity of matrix identities such as AB=I→BA=I

Categories

Keywords

Reprint years

DOI

10.1016/j.apal.2003.10.018

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,164

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Proving properties of matrices over \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathbb{Z}_{2}}$$\end{document}. [REVIEW]Michael Soltys - 2012 - Archive for Mathematical Logic 51 (5-6):535-551.
Teaching Linear Algebra at University.Jean-Luc Dorier - unknown
The finite model property for knotted extensions of propositional linear logic.C. J. van Alten - 2005 - Journal of Symbolic Logic 70 (1):84-98.
n‐linear weakly Heyting algebras.Sergio A. Celani - 2006 - Mathematical Logic Quarterly 52 (4):404-416.
Linear transformations in unitary geometric algebra.Garret Sobczyk - 1993 - Foundations of Physics 23 (10):1375-1385.
Planar and braided proof-nets for multiplicative linear logic with mix.G. Bellin & A. Fleury - 1998 - Archive for Mathematical Logic 37 (5-6):309-325.
Weak theories of linear algebra.Neil Thapen & Michael Soltys - 2005 - Archive for Mathematical Logic 44 (2):195-208.
Linear algebra representation of necker cubes 1: The crazy crate.C. Mortensen & S. Leishman - unknown
Real computation with least discrete advice: A complexity theory of nonuniform computability with applications to effective linear algebra.Martin Ziegler - 2012 - Annals of Pure and Applied Logic 163 (8):1108-1139.
A new correctness criterion for cyclic proof nets.V. Michele Abrusci & Elena Maringelli - 1998 - Journal of Logic, Language and Information 7 (4):449-459.
Quantified propositional calculus and a second-order theory for NC1.Stephen Cook & Tsuyoshi Morioka - 2005 - Archive for Mathematical Logic 44 (6):711-749.
The deduction rule and linear and near-linear proof simulations.Maria Luisa Bonet & Samuel R. Buss - 1993 - Journal of Symbolic Logic 58 (2):688-709.
Curry-Howard terms for linear logic.Frank A. Bäuerle, David Albrecht, John N. Crossley & John S. Jeavons - 1998 - Studia Logica 61 (2):223-235.
The Semantics and Proof Theory of Linear Logic.Arnon Avron - 1988 - Theoretical Computer Science 57 (2):161-184.

Analytics

Added to PP
2014-01-16

Downloads
11 (#1,070,627)

6 months
6 (#417,196)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

The complexity of propositional proofs.Nathan Segerlind - 2007 - Bulletin of Symbolic Logic 13 (4):417-481.
The proof complexity of linear algebra.Michael Soltys & Stephen Cook - 2004 - Annals of Pure and Applied Logic 130 (1-3):277-323.
Short propositional refutations for dense random 3CNF formulas.Sebastian Müller & Iddo Tzameret - 2014 - Annals of Pure and Applied Logic 165 (12):1864-1918.
Upper and lower Ramsey bounds in bounded arithmetic.Kerry Ojakian - 2005 - Annals of Pure and Applied Logic 135 (1-3):135-150.
Weak theories of linear algebra.Neil Thapen & Michael Soltys - 2005 - Archive for Mathematical Logic 44 (2):195-208.

View all 6 citations / Add more citations

References found in this work

The complexity of propositional proofs.Nathan Segerlind - 2007 - Bulletin of Symbolic Logic 13 (4):417-481.
The proof complexity of linear algebra.Michael Soltys & Stephen Cook - 2004 - Annals of Pure and Applied Logic 130 (1-3):277-323.
The complexity of propositional proofs.Alasdair Urquhart - 1995 - Bulletin of Symbolic Logic 1 (4):425-467.
An Introduction to Proof Theory.Samuel R. Buss - 2000 - Bulletin of Symbolic Logic 6 (4):464-465.

View all 7 references / Add more references