|
|||||
|
|
| 多项式时间复杂度的可计算实数域 | |
| 引用本文： | 李祥.多项式时间复杂度的可计算实数域[J].贵州科学,1983(1). |
| 作者姓名： | 李祥 |
| 作者单位： | 贵州大学 |
| 摘 要： | 近来,联系于著名的P与NP问题,开展了对构造分析(递归分析或可计算分析)的计算复杂性研究(见文献1]、2])。本文在Aberth的程序设计系统的计算模型里给出了两个可计算实数子类:多项式时间复杂度确定型可计算实数类PR与多项式时间复杂度非确定型可计算实数类NPR,证明了它们都是实数域与Rice可计算实数域的真子域。我们在该程序设计系统中引入了Oracle(神喻)集变元、Oracle函数变元以及随机变元,使用了Oracle指令与随机指令,从而建立了相对化的多项式时间复杂度可计 |
| 本文献已被 CNKI 等数据库收录！ | |