关于p－m度的分裂  

ON THE SPLITTING OF p-m DEGREES

作　　者：郑锡忠[1] 

机构地区：[1]南京大学数学系

出　　处：《软件学报》1994年第4期53-59,共7页Journal of Software

基　　金：国家自然科学基金

摘　　要：本文讨论多项式时间多一可化归度（ｐ－ｍ度）的分裂间题．主要结果是：存在非零的ｐ－ｍ度ａ，对任何自然数ｎ≥１当ａ分裂成ｎ＋１个度ａ０，ａ１，…，ａｎ的并时，其中至少有ｎ对（ａｉ，ａｊ）（ｉ≠ｊ；ｉ，ｊ≤ｎ）不是极小对．从而推广了Ａｍｂｏｓ－Ｓｐｉｅｓ中关于存在非零ｐ—ｍ度ａ不能分裂成一个极小对的结果．This paper discusses the splitting problem of the polynomial time bounded many one degrees. The main result is that: there exists a nonzero p-m degree a such that if a is splitted by n + 1 degrees a0, a1, ...,an for any natural number n≥1,then there exist at lesst n different pairs (ai,aj) (i≠j &. i,j≤n) which are not minimal paris. This generalizes Ambos-Spies' result of which asserts that there is a nonzero p-m degree which can not be splitted by any minimal pair.

关 键 词：分裂 p-m度 递归论 多项式 

分 类 号：TP301.4[自动化与计算机技术—计算机系统结构]