≤nphT极小集与Home-Spies猜测
-
摘要: 本文定义了在多项式时间界下不确定图灵纯正多项式归约的概念,讨论了子ph极小集的性质、‘旱p“极小集与‘早“极小集的关系。据此,对Homer一spies猜测提供了一个解答:p~Np当且仅当存在一个集合A,既是‘早”极小集,又是‘导P“极小集,且deg军“(A)=deg导p“(A)。
点击查看大图
计量
- 文章访问数: 714
- HTML全文浏览量: 50
- PDF下载量: 113
- 被引次数: 0