Enumerative counting is hard
- 1 January 1988
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 194-203
- https://doi.org/10.1109/sct.1988.5279
Abstract
An n-variable Boolean formula can have anywhere from 0 to 2/sup n/ satisfying assignments. The question of whether a polynomial-time machine, given such a formula, can reduce this exponential number of possibilities to a small number of possibilities is explored. Such a machine is called an enumerator, and it is proved that if there is a good polynomial-time enumerator for Hash P (i.e. one where the small set has at most O( mod f mod /sup 1-e/) numbers), then P=NP=P/sup Hash P/ and probabilistic polynomial time equals polynomial time. Furthermore, Hash P and enumerating Hash P are polynomial-time Turing equivalent.Keywords
This publication has 0 references indexed in Scilit: