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

• 作者: 温邦彦
• 来源期刊: 重庆理工大学学报（自然科学版）
• 学科: 数学
• 关键词: P NP 千禧年难题 计算复杂性 停机问题 对角线证法
• 年，卷（期）: 2010,（9）
• 页码范围: 108-126
• 分类号: O156
• 字数: 23986字
• 语种: 中文
• DOI: 10.3969/j.issn.1674-8425-B.2010.09.022

摘要

为了给出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上实现,建议基于逻辑学、多元函数论和算法优化理论建立计算复杂性的算题分类理论.对"停机问题"的不可判定结论提出了质疑,并且指出了对角线证法的错误.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	温邦彦	天津商业大学经济逻辑创新研究中心	2	6	2.0	2.0