本世纪之初，美国克雷研究所组织世界上有名的数学家，挑出了七个最重要的悬而未决的数学问题，涉及数学、理论物理、流体力学、计算机科学等学科。每一个问题悬赏一百万美元。这几个问题，有的对数学自身的发展具有深刻的理论意义，有的在某些方面对实践有重要的推动作用。这七个问题公布后，进一步得到国际科学界的关注，引发了全世界研究人员展开攻关研究。其中，2002年俄罗斯的佩雷尔曼成功解决了属于拓扑学领域的庞加莱猜想，被认为对理解人类所置身其中的物理世界有重要的意义。在他的成果得到公认后，这位俄罗斯学者因此成为风云人物，先后被授予数学界的最高奖菲尔兹奖以及克雷研究所的悬赏。

在这七个问题中，P vs NP问题是一个数学和理论计算机科学交叉领域的问题，提出于上世纪七十年代。P指确定型图灵机在多项式时间内可以求解的判定问题类，NP指非确定型图灵机在多项式时间内可以求解的判定问题类。P是NP的一个子集。P vs NP问题是，P与NP是否相等。NP类中最难的那些问题称为NPC问题。在实践中，已经发现几千个NPC问题，但是只具有对计算机来说难以有效运行的指数时间算法。在今年以前，还没有人找到NPC问题的被证明是正确的多项式时间算法，即证明P=NP。同时，也没有人成功证明NPC问题不存在多项式时间算法，即证明P不等于NP。国际科学界公认，这个问题是一个具有重大意义的未解决科学难题，甚至有可能是七个千禧年数学问题中最重要的一个。1986年，一位加拿大学者声称证明了P=NP，一年后被发现有错误。2010年，一位美国学者声称证明了P不等于NP，但是很快被否定。有学者曾经悲观地估计，这个问题有可能在2024或2050年才能解决。

如果一个组合优化问题不具有多项式时间算法，除非P=NP，那么它叫做NP难的。在多项式时间内返回近似可行解的算法称为近似算法，近似可行解的度量与最优解度量之比称为近似比。如果一个问题不具有一个特定的近似比，除非P=NP，那么这个问题称为不可近似的。NP难组合优化问题的近似算法及其不可近似性在计算机科学界已经成为一个主流的研究方向。半定规划算法（SDP），作为线性规划算法的推广，是一种求解对称矩阵仿射组合半正定约束条件下线性函数优化问题的内点算法，能够在问题输入规模的多项式时间内任意逼近问题的最优解。已经发现，在很多组合优化问题的松弛形式上应用半定规划算法和随机取整技术，能够证明目前已知的最佳甚至是紧密的近似比。上个世纪九十年代以来，在不可近似性研究领域相继出现了PCP定理，2P1R博弈，独裁者测试，离散傅立叶分析等重大理论成果。美国学者Khot和以色列学者Feige于2002年分别提出了两个关于NP难组合优化问题不可近似性的猜测UGC和FH。为了证实或者否定这两个猜测，各国学者取得了一系列阶段性结果，很多发表在计算机科学的两个顶级会议STOC和FOCS上。

中国人民大学信息资源管理学院崔鹏副教授在北京大学攻读博士学位期间，曾经从事计算复杂性和近似算法的研究。近年来，他关注UGC是否成立的问题，取得进展。他注意到，偏置取值和文字上的约束满足问题的平均复杂性能够推出UGC问题的更强的不可近似性结果。在此启发下，2014年初他得到了一个P=NP的证明：3SAT问题首先被归约到标签覆盖问题，再被归约到一个高维（10维以上）的加权约束满足问题的间隙问题，后者出人意料地能够用一个基于半定规划算法的近似算法BiLin求解，条件是这个加权约束满足问题的支持集合由三个特定的截断偏置按对独立分布组成。他的论文参考了国外两位年轻学者Chan和Hast的学术成果，并且引入了新的技术，即在独裁者测试中对验证者的问题作伪装以得到均衡按对独立分布的技术以及一个一次性消除证明者回答之间相关性的不变性定理。形象地说，他的新技术架起了连接可近似性和不可近似性的桥梁。3SAT问题能够在n^K时间内求解，n是问题输入规模，K是一个能够确定的很大的整数。

2014年2月，在经过内部研讨和检查后，崔鹏副教授在国际预印本网站Arxiv上公布了论文手稿，编号是1401.6520，并且在荷兰的P-versus-NP页面上登载了论文摘要，编号是103。这篇手稿公布后，已经在美国学者Lipton的Wordpress博客上引起了反响，被认为是一个严肃的结果。这篇手稿已经被推荐给一些知名的计算机科学家和国际计算机科学界的几个权威机构作同行评议。让我们共同期待“全世界数学家和计算机科学家放假一周”这一个美好时刻的到来。

                                     （供稿人：崔鹏）