Enumerative counting is hard

An n-variable Boolean formula may have anywhere from 0 to 2 n satisfying assignments. Can a polynomial-time machine, given such a formula, reduce this exponential number of possibilities to a small number of possibilities? We call such a machine an enumerator and prove that if there is a good polynomial-time enumerator for #P (i. e. , one where for every Boolean formula f, the small set has at most O(|f|1−ε ) numbers), then P = NP = P# P and probabilistic polynomial time equals polynomial time. Furthermore, we show that #P polynomial-time Turing reduces to enumerating #P.

Authors

• Jin-Yi Cai
• Lane A. Hemachandra

Keywords

No keywords are indexed for this paper.