Toward a Dichotomy Theorem for Polynomial Evaluation (2009)
Briquel, Irénée, Koiran, Pascal
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...
Toward a Dichotomy Theorem for Polynomial Evaluation (2009)
Briquel, Irénée, Koiran, Pascal
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...