闭包性质与 TotP 的特征化-计算机科学-计算复杂性-算法.pdfVIP

闭包性质与TotP的特征化

YaroslavIvanashev

HSEUniversity,FacultyofComputerScience,Moscow,101000,Russia

yivanashev@hse.ru

摘要类TotP包含计算非确定性多项式时间图灵机所有路径数量的函数。

在本文中，我们给出一个基于谓词定义的TotP，类似于#P的标准定义。

从对TotP的新特征化可以得出，许多众所周知的#P问题属于TotP，并且

本当且仅当PNP时属于TotP#P。我们证明了TotP具有#P和GapP

译的几个闭包性质，以及一些未知是否适用于#P和GapP的性质。我们还

证明了在左侧与FP进行复合运算下，TotP的闭包等价于TotPFP

中

和PPP，并给出了FP-函数的例子，使得如果TotP在其作用下的复

5合运算是封闭的，则它在与FP进行复合运算下也是封闭的。

v

2

6Keywords:计算复杂性·计数问题·闭包性质·#P.

2

0

2

.1介绍

4

0

5类TotP，在[17]中被引入，是包含计数非确定性多项式时间图灵机

2

:（NPTM）所有路径数量的函数的#P[23]的一个子类。在Section3中，我们给

v

i出了TotP的基于谓词的定义，在该定义中，它被描述为等于某种类型NP问

x

r题的见证数量的一类函数。从对TotP的新特征化中可以得出许多#P-问题

a

属于TotP，包括NonNegativePermanent,#PerfectMatchings,#DNF-Sat

和#NonCliques，它们在1-Cook还原下是#P-完全的。还得出，如果且

仅如果PNP，那么TotP#P。TotP在Karp还原[3]下具有完全问题，

并且与来自类#PE[20]的自归约函数在Karp还原下的闭包相吻合。TotP

利用区间大小函数进行特征描述在[7]中。在[6]中，研究了TotP与可逼近

函数类的关系。逻辑特性描述了TotP及其某些子类在[1,4,6]中给出。

TotP具有自然的闭包性质，例如，它在加法、乘法和减一[5]下是封闭

的。在Section4中，我们给出几个闭包性质，这些性质为TotP所有，而#P

和GapP具有[8,10]的性质，并且还存在一些未知是否适用于#P和GapP的

性质。在Section5中，我们给出了一个比GapPTotPFP[5]更精确的

2Y.Ivanashev

关于用TotP-函数刻画GapP的特征。在Section6中，我们研究了TotP在

与FP组合下的闭包（即是否为FPTotPTotP），并证明该陈述等价于