Title :
Resolution is not automatizable unless W[P] is tractable
Author :
Alekhnovich, Michael ; Razboro, A.A.
Author_Institution :
Inst. for Adv. Study, Princeton, NJ, USA
Abstract :
We show that neither Resolution nor tree-like Resolution is automatizable unless the class W[P] from the hierarchy of parameterized problems is fixed-parameter tractable by randomized algorithms with one-sided error.
Keywords :
computational complexity; interpolation; randomised algorithms; one-sided error; parameterized problems; randomized algorithms; tractable; tree-like Resolution; Computer science; Cryptography; Microwave integrated circuits; Polynomials; Quadratic programming;
Conference_Titel :
Foundations of Computer Science, 2001. Proceedings. 42nd IEEE Symposium on
Print_ISBN :
0-7695-1116-3
DOI :
10.1109/SFCS.2001.959895
