排序方式： 共有2条查询结果，搜索用时 0 毫秒
1
1.
戴东勇 《贵州大学学报(自然科学版)》1987,(1)
本文给出了三个相对化的 P 与 NP 的结果。在 S.Homer 及 W.Maass 的基础上,利用递归论中的优先方法,包括有穷损害优先方法。我们进一步研究相对化的 P 与 NP 问题的结构。比如,证明了存在两个互不可比的 P-禁集。此外,类似于递归中的算术分层及破分性,我们讨论了相对化多项式界计算的有关问题。 相似文献
2.
我们知道,都有a’》。,。全体Tu:ing-度D关于度的归约构成一个上半格。由于对任意的度于是跃变算子J:a令澎就是D到B一{b:b)汉}的一个映射。尸ri’ed。,g完全性准则证明了 产、沪产、八、碑产、以产、户J:D今B是满射。即对B中的任意元b,在D中都有一个原象a存在,使al二b。我们在本文中 产、尹尹、曰产、沪」气“‘,、产证明这个映射的每个象都有可数无穷个互不可比的原象存在。即 定理:对任意的度b)ol,存在一个递归独立序列{ai}i。。,使对一切i〔。有‘i飞一a iU‘)‘一b互1记号、定义及引理本文所需要的递归论知识可在文献〔1」,〔2]中… 相似文献
1