- 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.
- Links To Paper
- 1st Link
- Bibtex format
- @Article{EDI-INF-RR-0477,
- author = {
Martin Dyer
and Leslie Ann Goldberg
and Catherine Greenhill
and Mark Jerrum
},
- title = {The Relative Complexity of Approximate Counting Problems},
- journal = {Algorithmica},
- publisher = {Springer},
- year = 2003,
- month = {Dec},
- volume = {38(3)},
- pages = {471-500},
- doi = {10.1007/s00453-003-1073-y},
- url = {http://www.springerlink.com/link.asp?id=m557x2nhmkp5jpf0},
- }
|