The relative complexity of approximate counting problems
Dyer, Martin, Goldberg, Leslie Ann, Greenhill, Catherine and Jerrum, Mark, 1955-. (2004) The relative complexity of approximate counting problems. Algorithmica, Volume 38 (Number 3). pp. 471-500. ISSN 0178-4617Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/s00453-003-1073-y
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 > Computer Science|
|Journal or Publication Title:||Algorithmica|
|Official Date:||10 March 2004|
|Number of Pages:||30|
|Page Range:||pp. 471-500|
|Access rights to Published version:||Restricted or Subscription Access|
|Conference Paper Type:||Paper|
|Type of Event:||Workshop|
Actions (login required)