≤nphT极小集与Home-Spies猜测
-
摘要: 本文定义了在多项式时间界下不确定图灵纯正多项式归约的概念,讨论了子ph极小集的性质、‘旱p“极小集与‘早“极小集的关系。据此,对Homer一spies猜测提供了一个解答:p~Np当且仅当存在一个集合A,既是‘早”极小集,又是‘导P“极小集,且deg军“(A)=deg导p“(A)。
-

计量
- 文章访问数: 751
- HTML全文浏览量: 55
- PDF下载量: 113
- 被引次数: 0
引用本文: | 曾克和. ≤nphT极小集与Home-Spies猜测[J]. 西南交通大学学报, 1992, 5(3): 60-66. |