The proof complexity of linear algebra

DOI10.1016/j.apal.2003.10.018zbMath1059.03064OpenAlexW1967948656MaRDI QIDQ1886325

Michael Soltys, Stephen A. Cook

Publication date: 18 November 2004

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.apal.2003.10.018

zbMATH Keywords

Cayley-Hamilton theoremlinear algebraproof complexitypolynomial time reasoningBerkowitz's algorithmfeasible proofpolynomial size Frege proof

Mathematics Subject Classification ID

Matrix equations and identities (15A24) Basic linear algebra (15A99) Complexity of proofs (03F20)

Related Items (9)

The proof theoretic strength of the Steinitz exchange theorem ⋮ Proving properties of matrices over \({\mathbb{Z}_{2}}\) ⋮ Unnamed Item ⋮ Upper and lower Ramsey bounds in bounded arithmetic ⋮ Weak theories of linear algebra ⋮ The Complexity of Propositional Proofs ⋮ Short propositional refutations for dense random 3CNF formulas ⋮ Short Proofs for the Determinant Identities ⋮ LA, permutations, and the Hajós calculus

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Matrix identities and the pigeonhole principle
• On computing the determinant in small parallel time using a small number of processors
• The complexity of the pigeonhole principle
• A taxonomy of problems with fast parallel algorithms
• Polynomial size proofs of the propositional pigeonhole principle
• On Interpolation and Automatization for Frege Systems
• The Complexity of Propositional Proofs

This page was built for publication: The proof complexity of linear algebra