Back to Search
Start Over
On the Automatizability of Polynomial Calculus.
- Source :
- Theory of Computing Systems; Aug2010, Vol. 47 Issue 2, p491-506, 16p
- Publication Year :
- 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, ). [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 14324350
- Volume :
- 47
- Issue :
- 2
- Database :
- Complementary Index
- Journal :
- Theory of Computing Systems
- Publication Type :
- Academic Journal
- Accession number :
- 50808884
- Full Text :
- https://doi.org/10.1007/s00224-009-9195-5