Name
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 show a dichotomy theorem for polynomial evaluation. That is, we show that for a given set S, either there exists a VNP-complete family of polynomials associated to S, or the associated families of polynomials are all in VP. We give a concise characterization of the sets S that give rise to "easy" and "hard" polynomials. 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. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/978-3-642-03816-7_17 | MFCS |
Keywords | Field | DocType |
dichotomy theorem,associated family,polynomial evaluation,vnp-complete family,logical relation,hermann state,finite set,#p-completeness,constraint satisfaction problems,concise characterization,algebraic complexity,valiant's model,many-one reduction,turing reduction,constraint satisfaction problem | Discrete mathematics,#SAT,Combinatorics,Finite set,Existential quantification,Polynomial,Schaefer's dichotomy theorem,#P-complete,Constraint satisfaction problem,Counting problem,Mathematics | Conference |
Volume | ISSN | Citations |
5734 | 0302-9743 | 7 |
PageRank | References | Authors |
0.65 | 13 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Irénée Briquel | 1 | 11 | 1.43 |
| Pascal Koiran | 2 | 919 | 113.85 |