The strength of multilinear proofs

DOI10.1007/s00037-008-0246-0zbMath1174.03025OpenAlexW2074020517MaRDI QIDQ1024659

Ran Raz, Iddo Tzameret

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

zbMATH Keywords

Tseitin tautologiespolynomial calculusproof complexitypigeonhole principlemultilinear arithmetical formulas

Mathematics Subject Classification ID

Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20)

Related Items (4)

Characterizing Propositional Proofs as Noncommutative Formulas ⋮ Algebraic proofs over noncommutative formulas ⋮ Unnamed Item ⋮ Resolution over linear equations and multilinear proofs

This page was built for publication: The strength of multilinear proofs