
The Library
On the relative complexity of approximate counting problems
Tools
Dyer, Martin, Goldberg, Leslie Ann, Greenhill, Catherine and Jerrum, Mark (2000) On the relative complexity of approximate counting problems. University of Warwick. Department of Computer Science. (Department of Computer Science research report). (Unpublished)
|
PDF (Department of Computer Science Research Report)
WRAP_cs-rr-370.pdf - Other - Requires a PDF viewer. Download (463Kb) | Preview |
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.
Item Type: | Report | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Library of Congress Subject Headings (LCSH): | Counting, Computational complexity | ||||
Series Name: | Department of Computer Science research report | ||||
Publisher: | University of Warwick. Department of Computer Science | ||||
Official Date: | 28 February 2000 | ||||
Dates: |
|
||||
Number: | Number 370 | ||||
Number of Pages: | 30 | ||||
DOI: | CS-RR-370 | ||||
Institution: | University of Warwick | ||||
Theses Department: | Department of Computer Science | ||||
Status: | Not Peer Reviewed | ||||
Publication Status: | Unpublished | ||||
Funder: | Engineering and Physical Sciences Research Council (EPSRC), European Strategic Programme of Research and Development in Information Technology (ESPRIT), Leverhulme Trust (LT) | ||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
![]() |
View Item |