The Complexity of Counting Functions with Easy Decision Version
The Complexity of Counting Functions with Easy Decision Version
复制标题
使用 Easy Decision 版本计算函数的复杂性
DOI：
10.1007/11821069_64
复制
发表时间：
2006
影响因子：
2
通讯作者：
S. Zachos
中科院分区：
文献类型：
--
作者：
Aris Pagourtzis;S. Zachos
我们调查的复杂性计数问题，属于复杂性类#P，并有一个简单的决策版本。这些问题构成了#PE类，其中有一些著名的代表，如#Perfect Matchings，#DNF-Sat和NonNegative Permanent。这些问题的一个重要性质是它们都是Cook意义下的#P-完全问题，而除非P = NP，否则它们不能是Karp意义下的#P-完全问题。
我们研究这些问题的复杂性类TotP，其中包含的功能，计数的PNTM的所有路径的数量。我们首先将TotP与#P和#PE进行比较，并证明FP <$TotP <$#PE <$#P，并且包含是正确的，除非P = NP。
然后，我们证明了几个自然的#PE问题-包括上面提到的问题-属于TotP。证明了TotP是#PE的自约函数的Karp闭包。因此，所有这些问题都有一个显著的结构性质：对于它们中的每一个，都存在一个多项式时间的非确定性图灵机，它具有与输出值一样多的计算路径。
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⊆TotP⊆#PE⊆#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.