计数函数的低集-计算机科学-计算复杂性-算法.pdfVIP

计数函数的低集

YaroslavIvanashevEnvelopeOrcid

HSEUniversity,FacultyofComputerScience,Moscow,101000,Russia

Abstract

在本文中，我们刻画了计数函数类的低层次的语言和函数类别。类别#P和GapP的低层次恰好被刻

画为：Low(#P)=UP∩coUP和Low(GapP)=SPP。我们证明了Low(TotP)=P，Low(SpanP)=

NP∩coNP，并给出了低函数类对#P，GapP，TotP和SpanP的特征。我们建立了NPSV、UPSV和

tt

计数函数类之间的关系。对于这些类之间每一处包含关系，我们都给出了语言类之间等价的包含关系。

我们还证明了SpanP⊆GapP当且仅当NP⊆SPP，并且包含GapP+⊆SpanP蕴含PH=ΣP。对于

2

类#P,GapP,TotP和SpanP，我们总结已知结果并证明这些类在与FP+进行左复合时是封闭的当且仅

当它们坍缩为其低级函数类。

2012ACMSubjectClassificationTheoryofcomputation→Complexityclasses

本Keywordsandphrases计算复杂性，计数类，闭包性质，低层次问题

译

中

11介绍

v

0复杂性理论中的低度概念由Schöning引入，用于描述属于NP的且对多项式时间

1

1层次结构的级别[18]是低的那些语言。如果CL=C，则语言L对于可相对化的复

4

0杂性类C来说是低的。非正式地说，一个语言如果是低度的话，当它作为预言机使用

.

7时不会增加该类别的计算能力。某些复杂性类别的低类别已经被精确地表征。例如，

0Low(NP)=NP∩coNP[18]，Low(AM)=AM∩coAM[19]和Low(BPP)=BPP[25]。

5

2对于计数函数类#P[24]和GapP[5]，其低级类别也已知：Low(#P)=UP∩coUP[15]

:

v和Low(GapP)=SPP[5]。在本文中，我们给出了计数函数类TotP[12]和SpanP[13]的

i

x低级特征。我们也给出了低函数类对于#P,GapP,GapP+,TotP和SpanP的特征描述。结

r

a果总结在Table1中。特别是，我们证明了UPSV=Low(#P)和NPSV=Low(SpanP)。

tftf

类NPSV和UPSV分别是类NPSV和UPSV的子类，仅包含总函数[3,4]。在Section4

tt

中，我们建立了类NPSV、UPSV和计数函数类#P、GapP、TotP以及SpanP之间