%0 Journal Article
%T THE P-NP PROPERTIES OF BOUNDED QUERY COMPUTATIONS<br>受限外部信息源计算的P─NP性质
%A Lu Yizhong
%A Liu Jianbin
%A <br>吕义忠
%A 刘建斌
%J 软件学报
%D 1994
%I 
%X 本文对Ｏｒａｃｌｅ图灵机在接受计算中的查询次数加以限制，并且得到结果：存在无穷多个非多项式等价的递归集Ａ，Ｂ，Ａ′，Ｂ″，Ａ″，Ｂ″，Ａ，Ｂ，它们满足性质：Ｐ（Ａ，ｑ）＝Ｐ（Ａ，ｑ＋１），Ｐ（Ｂ，ｑ）≠Ｐ（Ｂ，ｑ＋１），ｐ（Ａ′，ｑ）＝Ｐ（Ａ′），Ｐ（Ｂ′，ｑ）≠Ｐ（Ｂ′）．ＮＰ（Ａ″，ｑ）＝ＮＰ（Ａ″，ｑ＋１），ＮＰ（Ｂ″，ｑ）≠ＮＰ（Ｂ″，ｑ＋１），ＮＰ（Ａ，ｑ）＝ＮＰ（Ａ），ＮＰ（Ｂ，ｑ）≠ＮＰ（Ｂ）．
%K Computational complexity
%K P-NP question
%K recursive set
%K oracle<br>计算复杂性，P─NP问题，递归集，外部信息源
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=7735F413D429542E610B3D6AC0D5EC59&aid=32AA742F30CA63E839F5033EC12829A7&yid=3EBE383EEA0A6494&vid=94C357A881DFC066&iid=E158A972A605785F&sid=1371F55DA51B6E64&eid=B6DA1AC076E37400&journal_id=1000-9825&journal_name=软件学报&referenced_num=0&reference_num=11