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. Comput. 38(4):1347-1363, 2008).
On the Automatizability of Polynomial Calculus / Galesi, Nicola; Lauria, Massimo. - In: THEORY OF COMPUTING SYSTEMS. - ISSN 1432-4350. - ELETTRONICO. - 47:2(2010), pp. 491-506. [10.1007/s00224-009-9195-5]
On the Automatizability of Polynomial Calculus
GALESI, NICOLA;LAURIA, MASSIMO
2010
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. Comput. 38(4):1347-1363, 2008).File allegati a questo prodotto
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
