节点文献

UP的相对完全性

The Relativized Completeness of UP

推荐 CAJ下载
PDF下载
不支持迅雷等下载工具，请取消加速工具后下载。

【Author】 Lü Yizhong Sun Huicheng Mathematics Department of Nanjing University,210008

【摘要】 [He 88]在第三部分“UP有图灵完全语言吗”?的标题下构造了一个递归Oracle A,并且证明UP~A 无图灵完全语言。本文构造了一个NP Oracle B 并且证明UP~B 有多项式完全语言(从而也就有图灵完全语言)。更多还原

【Abstract】 In section 3 of[He 88],under the title“Does UP have Turing Complete Languages?”the author constructs a recursive Oracle A such that UP~A has no Turing complete sets.In this paperWe construct an NP Oracle B such that UP~B does have Turing complete sets.更多还原

【关键词】图灵完全；构造算法；完全性； UP；完全集；多项式时间；结构复杂性；状态集；带符号；化归；

【文献出处】计算机研究与发展 ,Journal of Computer Research and Development , 编辑部邮箱 ,1991年02期

【下载频次】5

知网节下载

节点文献中：

本文链接的文献网络图示:

本文的引文网络

节点文献