The Relative Complexity of Approximate Counting Problems

被引：0

作者：

Martin Dyer

Leslie Ann Goldberg

Catherine Greenhill

Mark Jerrum

机构：

[1] School of Computing,

[2] University of Leeds,undefined

[3] Leeds LS2 9JT,undefined

[4] Department of Computer Science,undefined

[5] University of Warwick,undefined

[6] Coventry,undefined

[7] CV4 7AL,undefined

[8] Department of Mathematics and Statistics,undefined

[9] University of Melbourne,undefined

[10] Parkville,undefined

[11] Division of Informatics,undefined

[12] University of Edinburgh,undefined

[13] JCMB,undefined

[14] The King’s Buildings,undefined

[15] Edinburgh EH9 3JZ,undefined

来源：

Algorithmica | 2004年 / 38卷

关键词：

Approximate counting; Computational complexity;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

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.

引用

页码：471 / 500

页数：29