Informatics Report Series


Report   

EDI-INF-RR-0477


Related Pages

Report (by Number) Index
Report (by Date) Index
Author Index
Institute Index

Home
Title:The Relative Complexity of Approximate Counting Problems
Authors: Martin Dyer ; Leslie Ann Goldberg ; Catherine Greenhill ; Mark Jerrum
Date:Dec 2003
Publication Title:Algorithmica
Publisher:Springer
Publication Type:Journal Article Publication Status:Published
Volume No:38(3) Page Nos:471-500
DOI:10.1007/s00453-003-1073-y
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},
}


Home : Publications : Report 

Please mail <reports@inf.ed.ac.uk> with any changes or corrections.
Unless explicitly stated otherwise, all material is copyright The University of Edinburgh