On the Automatizability of Polynomial Calculus.
Nicola Galesi, Massimo Lauria · 2009
We prove that Polynomial Calculus and Polynomial Calculus with Resolution are not autom-atizable, unless W [P]-hard problems are fixed parameter tractable by one-side error randomized algorithms. This extends to Polynomial Calculus the analogous result obtained for Resolution by Alekhnovich and Razborov [2]. 1