P/NP问题的答案是P≠NP

作者：温邦彦pnp千禧年难题计算复杂性停机问题对角线证法

摘要：为了给出P/NP问题的答案,采用简单的逻辑分析法来证明,创造性地提出了定义的划分标准必须符合逻辑的相容性、功能的合旨性（符合划分目的、结果＂是＂＂非＂分明）、操作的明确性（验证含义明确、范畴＂虚＂＂实＂明确）的3条5点要求。对P和NP的定义作了逻辑的内涵和外延分析,由于NP定义中非确定性多项式算法所依赖的虚拟世界神奇假想,在现实世界中不可能成真,所以在多项式时间内得不出算题计算的正确结论,从而也就得不出分类结论（NP P）,由此证明了P/NP问题的答案是P≠NP。对＂难解类＂、＂P标准的验证含义＂、＂P是NP的子集＂作了辨析,证明：按照现有理解,P=NP和P≠NP2种证明任务都没法完成。2个定理正反双向证明了P≠NP结论的正确。还对＂梵塔算题属于P类＂提出了质疑,指出多项式变换只能在NTM上实现,建议基于逻辑学、多元函数论和算法优化理论建立计算复杂性的算题分类理论。对＂停机问题＂的不可判定结论提出了质疑,并且指出了对角线证法的错误。

注：因版权方要求，不能公开全文，如需全文，请咨询杂志社