| 摘要: |
| 本文讨论多项式时间多一可化归度（ｐ－ｍ度）的分裂间题．主要结果是：存在非零的ｐ－ｍ度ａ，对任何自然数ｎ≥１当ａ分裂成ｎ＋１个度ａ0，ａ1，…，ａn的并时，其中至少有ｎ对（ａi，ａj）（ｉ≠ｊ；ｉ，ｊ≤ｎ）不是极小对．从而推广了Ａｍｂｏｓ－Ｓｐｉｅｓ中关于存在非零ｐ—ｍ度ａ不能分裂成一个极小对的结果． |
| 关键词: p—m可化归度，极小对，分裂 |
| DOI： |
| 分类号: |
| 基金项目:国家自然科学基金 |
|
| ON THE SPLITTING OF p-m DEGREES |
|
Zheng Xizhong
|
| Abstract: |
| 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. |
| Key words: p-m reducibility degree minimal pair splitting. |
