| 摘要: |
| 本文对Ｏｒａｃｌｅ图灵机在接受计算中的查询次数加以限制，并且得到结果：存在无穷多个非多项式等价的递归集Ａ，Ｂ，Ａ′，Ｂ″，Ａ″，Ｂ″，Ａ，Ｂ，它们满足性质：Ｐ（Ａ，ｑ）＝Ｐ（Ａ，ｑ＋１），Ｐ（Ｂ，ｑ）≠Ｐ（Ｂ，ｑ＋１），ｐ（Ａ′，ｑ）＝Ｐ（Ａ′），Ｐ（Ｂ′，ｑ）≠Ｐ（Ｂ′）．ＮＰ（Ａ″，ｑ）＝ＮＰ（Ａ″，ｑ＋１），ＮＰ（Ｂ″，ｑ）≠ＮＰ（Ｂ″，ｑ＋１），ＮＰ（Ａ，ｑ）＝ＮＰ（Ａ），ＮＰ（Ｂ，ｑ）≠ＮＰ（Ｂ）． |
| 关键词: 计算复杂性，P─NP问题，递归集，外部信息源 |
| DOI： |
| 分类号: |
| 基金项目: |
|
| THE P-NP PROPERTIES OF BOUNDED QUERY COMPUTATIONS |
|
Lu Yizhong,Liu Jianbin
|
| Abstract: |
| his paper restricts oracle Turing machine to query its oracle in an accepting computation, and obtains result: there exist infinite number of recursive sets A, B, A',B', A", B", A, B, which are not equivalent satisfying properties: P(A,q) =P(A,q+ 1 ), P(B,q ) ≠P(B,q+1)p(a',q)=P(A' ),P(B',q)≠P(B' ),NP(A",q) = NP(A",q + 1),NP(B",q) ≠ (B",q+ 1 ),NP (A,q) =NP(A), NP(B,q)≠NP(B). |
| Key words: Computational complexity P-NP question recursive set oracle. |
