• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Symposium on Mathematical Foundations of Computer Science >The Complexity of Counting Functions with Easy Decision Version
【24h】

The Complexity of Counting Functions with Easy Decision Version

机译：简单决策版本计数功能的复杂性

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We investigate the complexity of counting problems that belong to the complexity class #P and have an easy decision version. These problems constitute the class #PE which has some well-known representatives such as #PERFECT MATCHINGS, #DNF-SAT, and NONNEGATIVE PERMANENT. An important property of these problems is that they are all #P-complete, in the Cook sense, while they cannot be #P-complete in the Karp sense unless P = NP. We study these problems in respect to the complexity class TotP, which contains functions that count the number of all paths of a PNTM. We first compare TotP to #P and #PE and show that FP is contained in TotP is contained in #PE is contained in #P and that the inclusions are proper unless P = NP. We then show that several natural #PE problems — including the ones mentioned above — belong to TotP. Moreover, we prove that TotP is exactly the Karp closure of self-reducible functions of #PE. Therefore, all these problems share a remarkable structural property: for each of them there exists a polynomial-time nondeterministic Turing machine which has as many computation paths as the output value.
机译：我们调查计算属于复杂性类#p的问题的复杂性，并且具有简单的决策版本。这些问题构成了班级#pe，它有一些着名的代表，如#perfect匹配，＃dnf-sat和非负永久性。这些问题的一个重要属性是它们都是＃p-temply，在厨师的意义上，除非p = np，否则它们不能在karp sense中排名第一。我们在复杂性类TOTP上研究这些问题，其中包含计算PNTM所有路径的函数。我们首先比较TOTP到#P和#PE，并显示FP包含在TOTP中，其中#pe包含在#p中，除非p = np，夹杂物是正确的。然后，我们表明了几个自然的#pe问题 - 包括上面提到的问题 - 属于Totp。此外，我们证明了TOTP正好是#PE的自我可重复函数的KARP闭合。因此，所有这些问题都具有显着的结构特性：对于它们中的每一个，存在具有作为输出值的计算路径的多项式非术语定义机器。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号