The complexity of counting problems

被引:0
|
作者
Welsh, D [1 ]
Gale, A [1 ]
机构
[1] Math Inst, Oxford OX1 3LB, England
关键词
D O I
暂无
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
These lectures are intended to cover various aspects of the complexity of counting problems. They are concentrated on the class of functions contained in the class #P, which is the counting counterpart of the language class NP. These notes are a mixture of theory and examples, taken mainly from pure mathematics and combinatories, Because of the apparent difficulty of most problems which arise naturally, there has been considerable effort put into good approximation schemes. This is reflected in these notes.
引用
收藏
页码:115 / 153
页数:39
相关论文
共 50 条
  • [1] Progress in Complexity of Counting Problems
    Cai, Jin-Yi
    FRONTIERS IN ALGORITHMICS AND ALGORITHMIC ASPECTS IN INFORMATION AND MANAGEMENT, (FAW-AAIM 2011), 2011, 6681 : 1 - 3
  • [2] The parameterized complexity of counting problems
    Flum, J
    Grohe, M
    SIAM JOURNAL ON COMPUTING, 2004, 33 (04) : 892 - 922
  • [3] The complexity of planar counting problems
    Hunt, HB
    Marathe, MV
    Radhakrishnan, V
    Stearns, RE
    SIAM JOURNAL ON COMPUTING, 1998, 27 (04) : 1142 - 1167
  • [4] The parameterized complexity of counting problems
    Flum, J
    Grohe, M
    FOCS 2002: 43RD ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 2002, : 538 - 547
  • [5] Counting Problems in Parameterized Complexity
    Zhang, Chihao
    Chen, Yijia
    TSINGHUA SCIENCE AND TECHNOLOGY, 2014, 19 (04) : 410 - 420
  • [6] Counting Problems in Parameterized Complexity
    Chihao Zhang
    Yijia Chen
    TsinghuaScienceandTechnology, 2014, 19 (04) : 410 - 420
  • [7] The Complexity of Counting Problems in Equational Matching
    Hermann, M.
    Kolaitis, P. G.
    Journal of Symbolic Computation, 20 (03):
  • [8] Complexity of generalized satisfiability counting problems
    Creignou, N
    Hermann, M
    INFORMATION AND COMPUTATION, 1996, 125 (01) : 1 - 12
  • [9] RATIONAL TRANSDUCTIONS AND COMPLEXITY OF COUNTING PROBLEMS
    CHOFFRUT, C
    GOLDWURM, M
    MATHEMATICAL SYSTEMS THEORY, 1995, 28 (05): : 437 - 450
  • [10] Complexity of Generalized Satisfiability Counting Problems
    Dept. de Mathématiques, Université de Caen, 14032 Caen, France
    不详
    Inf Comput, 1 (1-12):