ALCOMFT-TR-01-6

Martin Dyer, Leslie Ann Goldberg, Catherine Greenhill and Mark Jerrum
On the relative complexity of approximate counting problems
Warwick. Work package 4. January 2001.

Abstract: Two natural classes of counting problems that are interreducible under approximation-preserving reductions are: (i) those that admit a particular kind of efficient approximation algorithm known as an ``FPRAS,'' and (ii) those that are complete for #P with respect to approximation-preserving reducibility. We describe and investigate not only these two classes but also a third class, of intermediate complexity, that is not known to be identical to (i) or (ii). The third class can be characterised as the hardest problems in a logically defined subclass of #P.

Postscript file: ALCOMFT-TR-01-6.ps.gz (162 kb).