-
题名复杂性集类的集合剖分
- 1
-
-
作者
黄文奇
陈志祥
-
机构
华中科技大学
-
出处
《数学年刊(A辑)》
CSCD
北大核心
1989年第5期565-570,共6页
-
基金
中国科学院科学基金
-
文摘
本文证明了一个一般性的关于复杂性集类集合剖分的定理。此定理叙述如下:设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-极小对。
-
关键词
复杂性集类
集合剖分
递归论
-
分类号
O141.3
[理学—基础数学]
-
-
题名一类集合剖分的等幂和问题
- 2
-
-
作者
王其提
徐巧石(指导)
-
机构
江苏省海门中学
-
出处
《数学通讯》
2022年第1期54-56,共3页
-
文摘
本文从几个富有启发性的问题出发,探究一类集合剖分的等幂和问题,得到了一般情况下的结论,介绍了具体的构造方法.
-
关键词
集合剖分
等幂和问题
推广探究
一般结论
构造方法
-
分类号
G63
[文化科学—教育学]
-