受限外部信息源计算的P─NP性质

THE P-NP PROPERTIES OF BOUNDED QUERY COMPUTATIONS

本文对Ｏｒａｃｌｅ图灵机在接受计算中的查询次数加以限制，并且得到结果：存在无穷多个非多项式等价的递归集Ａ，Ｂ，Ａ′，Ｂ″，Ａ″，Ｂ″，Ａ，Ｂ，它们满足性质：Ｐ（Ａ，ｑ）＝Ｐ（Ａ，ｑ＋１），Ｐ（Ｂ，ｑ）≠Ｐ（Ｂ，ｑ＋１），ｐ（Ａ′，ｑ）＝Ｐ（Ａ′），Ｐ（Ｂ′，ｑ）≠Ｐ（Ｂ′）．ＮＰ（Ａ″，ｑ）＝ＮＰ（Ａ″，ｑ＋１），ＮＰ（Ｂ″，ｑ）≠ＮＰ（Ｂ″，ｑ＋１），ＮＰ（Ａ，ｑ）＝ＮＰ（Ａ），ＮＰ（Ｂ，ｑ）≠ＮＰ（Ｂ）．

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).