| Toward a Dichotomy Theorem for Polynomial Evaluation (2009) | |||||||||||||
Abstract | |||||||||||||
| A dichotomy theorem for counting problems due to Creignou and Hermann states that or any finite set S of logical relations, the counting problem # SAT (S) is either in FP, or #P-complete. In the present paper we study polynomial evaluation from this dichotomic point of view. We show that the "hard" cases in the Creignou-Hermann theorem give rise to VNP-complete families of polynomials, and we give partial results for the "easy" case of this dichotomy theorem. We also prove that several problems which were known to be #P-complete under Turing reductions only are in fact #P-complete under many-one reductions. | |||||||||||||
Publication details | |||||||||||||
| |||||||||||||