O’下纯正多项式极小度的存在性

数学季刊 ›› 1987, Vol. 2 ›› Issue (2): 21-26.

O’下纯正多项式极小度的存在性

中国科学院软件研究所

收稿日期:1986-10-23 出版日期:1987-06-30 发布日期:2021-01-26

The Existence of Minimal Honest Polynomial Degree Below O’

中国科学院软件研究所

Received:1986-10-23 Online:1987-06-30 Published:2021-01-26

摘要/Abstract

摘要： 引言Homer 在中证明了在 P=NP 条件下可以证明 O′下纯正多项式极小度的存在性,他还证明了若干种 O″下的集不具有纯正多项式极小度.如果可以证明一切 O″下的集都不具有纯正极小度,那么可以证明 P≠NP。因此 Homer 的工作给出了一个解决“P=?NP”问题的一个可能途径.本文目的是在 P=NP 条件下证明在 O′下存在纯正多项式极小度.这样只须证明一切O′下的集都不具有纯正多项式极小度,则有 P≠NP.从而可以使证明 P≠NP 的这种途径

Abstract: 引言Homer 在中证明了在 P=NP 条件下可以证明 O′下纯正多项式极小度的存在性,他还证明了若干种 O″下的集不具有纯正多项式极小度.如果可以证明一切 O″下的集都不具有纯正极小度,那么可以证明 P≠NP。因此 Homer 的工作给出了一个解决“P=?NP”问题的一个可能途径.本文目的是在 P=NP 条件下证明在 O′下存在纯正多项式极小度.这样只须证明一切O′下的集都不具有纯正多项式极小度,则有 P≠NP.从而可以使证明 P≠NP 的这种途径

杨东屏. O’下纯正多项式极小度的存在性[J]. 数学季刊, 1987, 2(2): 21-26.

YANG Dong-ping. The Existence of Minimal Honest Polynomial Degree Below O’[J]. Chinese Quarterly Journal of Mathematics, 1987, 2(2): 21-26.