The strength of multilinear proofs
From MaRDI portal
Publication:1024659
DOI10.1007/s00037-008-0246-0zbMath1174.03025MaRDI QIDQ1024659
Publication date: 17 June 2009
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-008-0246-0
Tseitin tautologies; polynomial calculus; proof complexity; pigeonhole principle; multilinear arithmetical formulas
13P10: Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
03F20: Complexity of proofs
Related Items
Characterizing Propositional Proofs as Noncommutative Formulas, Unnamed Item, Algebraic proofs over noncommutative formulas, Resolution over linear equations and multilinear proofs