Dyer, Martin, Goldberg, Leslie Ann, Greenhill, Catherine and Jerrum, Mark (2004) The relative complexity of approximate counting problems. Algorithmica, Volume 38 (Number 3). pp. 471-500. doi:10.1007/s00453-003-1073-y ISSN 0178-4617.

Research output not available from this repository.

Request-a-Copy directly from author or use local Library Get it For Me service.

Request Changes to record.

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:	Journal Article
Subjects:	Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software Q Science > QA Mathematics
Divisions:	Faculty of Science, Engineering and Medicine > Science > Computer Science
Journal or Publication Title:	Algorithmica
Publisher:	Springer Verlag
ISSN:	0178-4617
Official Date:	10 March 2004
Dates:	Date Event 10 March 2004 Published
Volume:	Volume 38
Number:	Number 3
Number of Pages:	30
Page Range:	pp. 471-500
DOI:	10.1007/s00453-003-1073-y
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
Conference Paper Type:	Paper
Type of Event:	Workshop

Data sourced from Thomson Reuters' Web of Knowledge

Request changes or add full text files to a record

Repository staff actions (login required)

View Item