Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR09-035 | 26th March 2009 00:00

On the Automatizability of Polynomial Calculus

RSS-Feed




TR09-035
Authors: Nicola Galesi, Massimo Lauria
Publication: 23rd April 2009 17:38
Downloads: 3430
Keywords: 


Abstract:

We prove that Polynomial Calculus and Polynomial Calculus with Resolution are not automatizable, 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 (SIAM J. Computing, 38(4), 2008).



ISSN 1433-8092 | Imprint