Lower bounds for polynomial calculus in the case of nonbinomial ideals.

zbMath1063.68589MaRDI QIDQ1432645

Alexander A. Razborov, M. V. Alekhnovich

Publication date: 15 June 2004

Published in: Doklady Mathematics (Search for Journal in Brave)

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20)

Related Items (6)

Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas ⋮ Characterization of robust immune symmetric Boolean functions ⋮ Algebraic proof systems over formulas. ⋮ Algebraic Attacks against Random Local Functions and Their Countermeasures ⋮ Toward a model for backtracking and dynamic programming ⋮ On the automatizability of polynomial calculus

This page was built for publication: Lower bounds for polynomial calculus in the case of nonbinomial ideals.