复杂性集类的集合剖分

本文证明了一个一般性的关于复杂性集类集合剖分的定理。此定理叙述如下:设C_1、C_2是二递归集类,C_1(?)P,C_1与C_2均递归可表现,C_1封闭于有限对称差,C_2中之集均无穷。则对任意的递归集A(?)C1∪C2,存在B_i、D_i(i=1,2,3)剖分A,使得1)B_i、D_i(?)C1∪C_2;2)B_i、D_i≤_m~pA;3)B_i、D_i是C_2禁集;4)(B_i,D_i)是p-极小对。由此定理可直接推出许多有趣结果,例如,假设P≠NP,则对任何A∈NP-(P∪NPT),存在B_i、D_i(i=1,2,3)∈NP-(P∪NPT)剖分A,使得1)B_i、D_i是NPT禁集;2)(B_i,D_i)是P-极小对。