Name
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). |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/s00224-009-9195-5 | Theory of Computing Systems / Mathematical Systems Theory |
Keywords | DocType | Volume |
Automatizability,Polynomial calculus,Proof complexity,Degree lower bound | Journal | 47 |
Issue | ISSN | Citations |
2 | 1432-4350 | 5 |
PageRank | References | Authors |
0.40 | 16 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nicola Galesi | 1 | 367 | 28.05 |
| Massimo Lauria | 2 | 122 | 14.73 |