论文部分内容阅读
本文定义了在多项式时间界下不确定图灵纯正多项式归约(记为≤_T~(n p h))的概念,讨论了≤_T~(n p h)极小集的性质、≤_T~(n p h)极小集与≤_T~(p h)极小集的关系。据此,对Homer-Spies猜测提供了一个解答:P=NP当且仅当存在一个集合A,既是≤_T~(p h)极小集,又是≤_T~(n p h)极小集,且deg_T~(p h)(A)=deg_T~(n p h)(A)。