我们的NP理论工作首重解读NP的二个流行定义及二个定义的关系，这篇英语文章是此工作的总结和深化。 文章追本溯源分析用于定义NP的NDTM（不确定性图灵机），揭示NDTM指称二个完全不同的概念：一个是Oracle（神喻机），另一个是Turing Machine（图灵机）。由于同一术语NDTM指称两个内涵完全不同的概念，故发生了“概念偷换”的逻辑错误，导致“可验证”成为现在NP的标准定义，自此NP的本质“不确定性”消失了，遂有“P versus NP”的千禧年难题。 由于NP的原始定义与Oracle有关，而Oracle又来自图灵关于“可计算性”的工作，故追本溯源到图灵的工作，应该是澄清NP定义的正途，也即我们的NP理论基于可计算性的深刻背景。 ＊＊＊＊＊＊ In this paper, we interpret NDTM (NonDeterministicTuringMachine) used to define NP by tracing to the source of NP . Originally NP was defined as the class of problems solvable in polynomial time by a NDTM in Cook’s theorem, where the NDTM was represented as Query Machine of essence Oracle . Later a model consisting of a guessing module and a checking module was proposed to replace the NDTM . This model of essence TM has a fundamental difference from the NDTM of essence Oracle , but people still use the term NDTM to designate this model, which leads to the disguised displacement of NDTM and produces out the verifier-based definition of NP as the class of problems verifiable in polynomialtime by a TM (Turing Machine). This verifier-based one has been then accepted as the standard definition of NP where comes from the famous equivalence ofthe two definitions of NP . Since then the notion of nondeterminism is lost from NP , which causes ambiguities in understanding NP and then great difficulties in solving the P versus NP problem. Since NP is originally related with Oracle that comes from Turing’s work about Computability , it seems quite necessary to trace back to Turing’s work and clarify further the issue about NP . interpretationNDTMCiE.pdf
－ 科学的每一部门都是对于整个自然界的一种描述，而这种描述通常都是近似性的。事实上，每件我们所知道的事都不外是对真理的一种近似叙述……我们现在学习的态度就是准备随时放弃或更正。《费因曼物理学》 － 物有本末，事有终始，知所先后，则近道矣。《大学》 《紐約客》科普“P versus NP”，通俗、精简地介绍了这个著名的“千禧年难题”（ 《紐約客》科普“P versus NP”（MAY 2, 2013） ）。此外还有美剧《基本演绎法》（Elementary，又译：现代福尔摩斯）的第2季第2集中也谈及此问题，说两位研究NP问题的数学家被谋杀了，凶手是同行，因为被害者即将证明“P=NP问题”，她为独吞成果而下了毒手。剧中只用了一句话来介绍 P=NP的意义：“能用电脑快速验证一个解的问题，也能够用电脑快速地求出解”。 媒体把“P versus NP”这样高居庙堂的理论问题带入了普通人们的视野，是谓“旧时王谢堂前燕，飞入寻常百姓家”，这正反映了计算机给当代社会所带来的深刻变化和影响。然而，这样的科普，一方面能使外行多少知道这个问题的大概情况，另一方面，可能使很多“内行”更糊涂，因为作者是按现有的理论框架来介绍“P versus NP”的，并没有意识到该问题真正的困难所在。在此意义上，《紐約客》上的文章不仅是大众的好奇，更是专家的困惑，也正是作者所指出的这个问题在诸“千禧年”难题中的特殊性。 我们认为，导致“P versus NP”成为“世纪难题”的根本原因，在于NP的流行定义（多项式时间可验证）导致了NP的本质“不确定性”的消失，从而暗中肯定了“NP＝P”，然而就一般的常识而言，人们又直觉：NP ≠ P，如此致“P versus NP”成为悖论，乃至“世纪难题”。所以，“P versus NP”的真正难度并不在答“NP＝P？”，而在问“什么是NP？” 现代管理学之父彼得•德鲁克（Peter Drucker）将要离世的时候，做出一个这样的结论：“在管理决策中最常见的错误，是我们强调寻找正确的答案，而不是正确的问题。”他还说：“最严重的错误，不是回答错误，真正危险的事，是问错了问题。”此现象不仅仅表现在管理决策中，更见诸于生活中的方方面面，或许可以说，这是人的认知的最大盲点。 那么，为什么“问题”如此重要？因为“问题”是认知和行为的原点，围绕着“问题”整个思想和行动才得以展开，也就是说，“问题”界定、打造了我们面对的现实，指引着我们行动的方向。就NP而言，最初是相对P提出来的，即欲区别于已知的具有“确定性”本质的P，然而流行的观念却是“多项式时间可验证”的NP（Nondeterministic Polynomial time），但这样的性质是“确定性”的，是有NP的“不确定性”消失，P与NP的混淆。 我们NP理论工作，旨在算法理论层次上，理清相对于P的NP的概念内涵，即理清在“可计算性”意义上的“确定性”与“不确定性”的关系。“不确定性”这个概念的内涵，远远超过了算法理论这个层次，但在算法理论这个层次理清这个概念，无疑是最基本和最严格的工作。当然，这样的工作需大家参与、达成共识，这本身就是一项艰巨的集体性工作。 在此意义上，我们认为，探讨“P versus NP”这个问题的另一种意义，就是对知识界的整个认知的一个提高，由此我们或许可以理解Hemaspaandra在介绍Gasarch于2012年进行的第二次“P versus NP”调查时的悲叹（ http://blog.sciencenet.cn/blog-2322490-856768.html ）： －我希望在遥远的未来，当人们读到这四篇文章，可以帮助他们了解，在“P versus NP”还没得到解决的黑暗年代里人们的思想状态（I hope that people in the distant future will look at these four articles to help get a sense of people’s thoughts back in the dark ages when P versus NP had not yet been resolved。） 附曾经写的三篇点评《紐約客》文的博文： －点评《紐約客》文－流行的NP定义（1）： http://blog.sciencenet.cn/home.php?mod=spaceuid=2322490do=blogquickforward=1id=891584 －点评《紐約客》文－流行的NP定义（2）： http://blog.sciencenet.cn/blog-2322490-892261.html －点评《紐約客》文－流行的NP定义（3）： http://blog.sciencenet.cn/blog-2322490-893312.html
“P versus NP”是计算机理论最重要的议题，与人工智能的诸基本议题也密切相关。这是《紐約客》（The New Yorker）2013年5月科普“P versus NP”的文章，我们将之译出与大家分享： ＊＊＊＊＊＊ 最深刻的数学问题 2010年8月6日，一个叫Vinay Deolalikar的计算机科学家发表了一篇论文，题目简洁、大胆：“P≠NP”。如果Deolalikar是对的，他就解开了数学上系得最紧的一个结。2000年，P = NP问题被克莱数学研究所指定为七个千禧年难题之一 －“多年未解决的重要的经典问题”－到目前为止，只有其中一个被解决了 （庞加莱猜想于2003年由深居简出的俄罗斯数学家Grigory Perelman解决了，但他拒绝领取百万美元的奖金）。 一些克莱问题是由来已久的令人摸不到头的问题，例如，黎曼假设，首次亮相于1859年。相反，P versus NP却相对年轻，由多伦多的数学理论家Stephen Cook于1971年在题为“定理证明过程的复杂性（The complexity of theorem-proving procedures）”的文章中引入的，尽管此问题于更早二十年前，被由David Foster Wallace称为“现代数学绝对黑暗王子”的Kurt Gödel在一封信中已提到，这是一个包含三个字母魔鬼般的问题：P（我们可以容易解决的问题）等于NP（我们可以容易验证的问题）吗？ 以你的电子邮件密码为例，它的正确性在你敲回车键后一纳秒内就可验证。但某人想找你的密码却可能是徒劳的追求，涉及近乎无限多字母-数字排列，需几个世纪的试错。 Deolalikar实际上是说，总是会有一些问题我们可以识别答案，却不能快速找到答案的棘手问题 － 超出了我们最强大的微处理器能力。总有未解决的问题，答案未知。 如果Deolalikar的大胆证明成立，他不仅能辞去作为惠普研究员的日常工作，而且有理由期待作为当代一位伟大的数学家进入神殿。但是，这样的荣耀没有到来，计算机科学家和数学家如带血的鲨鱼般凶猛去审查Deolalikar的证明 － 证明有几十个定点的逻辑流程和k -SAT结构及其他类似的东西。麻省理工学院的计算理论家Scott Aaronson（为这篇文章的可靠性我咨询过他）在他的博客中写到，“如果Vinay Deolalikar因他的P≠NP证明被授予1,000,000美元克莱千禧年奖，那么我，Scott Aaronson，将私人补充他200,000美元。”前不久Deolalikar的论文颜面扫地，Moshe Vardi博士，Rice大学计算机科学教授，告诉“纽约时报” ：“我认为Deolalikar只赢得了15分钟的名望”。 Lance Fortnow他的新书“金獎券：P，NP，寻找不可能”中介绍，P versus NP是“数学中一个重大的没有解决的问题”，不仅因为它非常难以解决，而且因为它具有明显的实际应用价值。这是一个彻底简单、相信存在着能计算几乎所有东西的有效方法的梦想，“从治愈绝症到宇宙的性质”，甚至“认识无穷的算法过程。”所以，解决Birch和Swinnerton-Dyer猜想，另一个克莱千禧年大奖问题，尽管也是令人印象深刻的壮举，但却没有比明确证明任何问题能快速验证（NP）、也能快速解决（P）来得有实际意义。 Fortnow的书名取自“查理和巧克力工厂”－ 金獎券本身作为奖品颁发给广大的读者，虽然你可能会后悔在上微积分课时没有付出稍多的关注。读“金獎券”书是有点像看没有字幕的外语电影，你会错过一些东西，但不是全部，里面有一些数学的幽默，有趣、俗气和可爱，恰好就像你认为的数学家的幽默那样有趣、俗气和可爱。 被Fortnow称为“P”代表多项式时间，这意味着输入规模的次数为一个常数，如2或3。 相反地，指数时间是指数是输入规模。虽然多项式时间可能很长（例如，50^2），但比起指数（2^50）算不了什么。 如果前者是阿迪朗达克山，后者就是喜马拉雅山。当解决问题时，如果我们希望还有时间吃午饭的话，就希望计算时间保持在多项式时间内。 “NP”（非确定型多项式时间）是一组解决起来有不同难度的问题，许多日常活动与NP问题有关：现代计算机加密，例如，其中涉及非常大的素数分解。大约四十年前，Richard Karp，伯克利的理论家，首先识别了21问题是“NP完全”，这意味着它们至少与别的NP问题一样难。NP完全问题像是计算难度的密室，解决一个，其他的就解决了，更何况所有潜伏在后面的比NP小的问题。Karp预测一堆问题，像“有向哈密顿圈 ”和“顶点覆盖”，虽然他们很难解决，但解却易于验证。一个人也许能够通过苏联数学家所谓的“perebor”，Fortnow翻译为“强力搜索”解决这些问题，P versus NP问题指一个更快的方法是否存在。 到目前为止，答案是否定的。举其中的一个NP完全问题为例，“K-clique”，Fortnow解释如下：“什么是Facebook上最大团伙，使得在此团伙中的所有人都互相是朋友？”很显然，Facebook上的用户越多，找到这样的最大团伙就越困难，到目前为止，也还没有发现能有效寻找最大团伙的算法。然而，此问题解决了，任何一个同级的NP完全问题就解决了，这也就是为什么大多数人都认为P≠NP。 也有超出了数学的考虑。 Aaronson，麻省理工学院的科学家，写了一篇博文解释为什么他认为P≠NP，他提出了十大理由，其中第九条理由称作“哲学立论”：“如果P = NP，那么这个世界就完全不是我们通常认为的那样了，创造就不会有特殊的价值，在求解问题和验证问题之间就不存在根本的差距，每个能欣赏交响乐的人就是莫扎特，每个会一步一步进行数学证明的人就是高斯，每个能识别好的投资策略的人就是沃伦·巴菲特了。” 我们一直在评价小说的文学价值；多数评论家可以很轻松地把使一本小说了不起的单子放在一起。想象一下，现在，如果你可以写一个算法，来有效验证优秀小说，它并不像你想象的那么怪：早在2008年，俄罗斯作家Alexander Prokopovich就“写”了小说“真爱”，通过用计算机在72小时内重组17部经典著作。如Prokopovich告诉圣彼得堡时报 “今天出版社用最快的书创造的这样或那样的风格，迎合这样或那样读者受众的不同方法。 我们的程序可以帮助此工作”，然后，他加了一个注解：“不过，该方案不可能是一个作家，如Photoshop永远不是拉斐尔”。但是，如果P = NP，那么想出了如何用数学的效率创造“伟大”的小说和绘画，只是一个时间问题。 Fortnow的书花大量的篇幅描绘一个世界，P被证明等于NP，一个计算极乐的世界。 他设想，例如，肿瘤学家不用再有化疗的试验和错误的尝试，因为我们现在可以考察一个人的DNA，以及突变的DNA的癌细胞和变化的蛋白质，用正确的方式有效地折叠饿死癌细胞，而不会对正常细胞造成任何问题。他还举例政治丑闻，一个竞选人“聘请一名电脑程序员，下载十年内的数以万计的受欢迎的演讲，程序员然后用算法开发一个基于对当前事件的新的讲演”，博得不知情的市民可预见的拥戴。 把P≠NP作为公设，如Fortnow所说，就是允许世界有神秘、困难和挫折 － 也有发现和调查，令人愉快迟到的乐趣。 Fortnow承认存在着这种可能性“它永远是数学和科学上的一个真正伟大的奥秘”，然而，Vinay Deolalikar不太可能是最后一个去尝试证明的人，因为数学是建立在根本的傲慢之上的，即可以将Wallace Stevens所说的“一个不修边幅的荒野”整理的信念。这是一个必要的信念，但我们并不因此总是被奖励。 附“纽约客”的原文（http://www.newyorker.com/tech/elements/a-most-profound-math-problem）： May 2, 2013 (The New Yorker) A Most Profound Math Problem By Alexander Nazaryan On August 6, 2010, a computer scientist named Vinay Deolalikar published a paper with a name as concise as it was audacious: “P ≠ NP.” If Deolalikar was right, he had cut one of mathematics’ most tightly tied Gordian knots. In 2000, the P = NP problem was designated by the Clay Mathematics Institute as one of seven Millennium Problems—“important classic questions that have resisted solution for many years”—only one of which has been solved since. (The Poincaré Conjecture was vanquished in 2003 by the reclusive Russian mathematician Grigory Perelman, who refused the attached million-dollar prize.) A few of the Clay problems are long-standing head-scratchers. The Riemann hypothesis, for example, made its debut in 1859. By contrast, P versus NP is relatively young, having been introduced by the University of Toronto mathematical theorist Stephen Cook in 1971, in a paper titled “The complexity of theorem-proving procedures,” though it had been touched upon two decades earlier in a letter by Kurt Gödel, whom David Foster Wallace branded “modern math’s absolute Prince of Darkness.” The question inherent in those three letters is a devilish one: Does P (problems that we can easily solve) equal NP (problems that we can easily check)? Take your e-mail password as an analogy. Its veracity is checked within a nanosecond of your hitting the return key. But for someone to solve your password would probably be a fruitless pursuit, involving a near-infinite number of letter-number permutations—a trial and error lasting centuries upon centuries. Deolalikar was saying, in essence, that there will always be some problems for which we can recognize an answer without being able to quickly find one—intractable problems that lie beyond the grasp of even our most powerful microprocessors, that consign us to a world that will never be quite as easy as some futurists would have us believe. There always will be problems unsolved, answers unknown. If Deolalikar’s audacious proof were to hold, he could not only quit his day job as a researcher for Hewlett-Packard but rightly expect to enter the pantheon as one of the day’s great mathematicians. But such glory was not forthcoming. Computer scientists and mathematicians went at Deolalikar’s proof—which runs to dozens of pages of fixed-point logistics and k-SAT structures and other such goodies—with the ferocity of sharks in the presence of blood. The M.I.T. computational theorist Scott Aaronson (with whom I consulted on this essay’s factual assertions) wrote on his blog, If Vinay Deolalikar is awarded the $1,000,000 Clay Millennium Prize for his proof P≠NP, then I, Scott Aaronson, will personally supplement his prize by the amount of $200,000. It wasn’t long before Deolalikar’s paper was thoroughly discredited, with Dr. Moshe Vardi, a computer-science professor at Rice University, telling the Times, “I think Deolalikar got his 15 minutes of fame.” As Lance Fortnow describes in his new book, “The Golden Ticket: P, NP and the Search for the Impossible,” P versus NP is “one of the great open problems in all of mathematics” not only because it is extremely difficult to solve but because it has such obvious practical applications. It is the dream of total ease, of the confidence that there is an efficient way to calculate nearly everything, “from cures to deadly diseases to the nature of the universe,” even “an algorithmic process to recognize greatness.” So while a solution for the Birch and Swinnerton-Dyer conjecture, another of the Clay Millennium Prize problems, would be an impressive feat, it would have less practical application than definitive proof that anything we are able to quickly check (NP), we can also quickly solve (P). Fortnow’s book—which, yes, takes its name from “Willy Wonka the Chocolate Factory”—bills itself as a primer for the general reader, though you will likely regret not having paid slightly more attention during calculus class. Reading “The Golden Ticket” is sort of like watching a movie in a foreign language without captions. You will miss some things, but not everything. There is some math humor, which is at once amusing, cheesy, and endearing exactly in the way that you think a mathematician’s humor might be amusing, cheesy, and endearing. What Fortnow calls “P” stands for polynomial time, meaning the size of the input raised to a fixed number like two or three. Conversely, exponential time is some number raised to the size of the input. Though polynomial time can be long (say, 502), it is nothing compared to its exponential opposite (250). If the first is the Adirondacks, the second is the Himalayas. When solving things, we want to keep them in polynomial time if we still want to have time for lunch. “NP” (nondeterministic polynomial time) is a set of problems we want to solve, of varying degrees of difficulty. Many everyday activities rely on NP problems: modern computer encryption, for example, which involves the prime factors of extremely large numbers. Some forty years ago, Richard Karp, the Berkeley theoretician, first identified twenty-one problems as being “NP-complete,” meaning that they are at least as hard as any other NP problem. The NP-complete problems are a sort of inner sanctum of computational difficulty; solve one and you’ve solved them all, not to mention all the lesser NP problems lurking in the rear. Karp’s foreboding bunch of problems have names like “directed Hamiltonian cycle” and “vertex cover.” Though they are extremely hard to solve, solutions are easy to check. A human may be able to solve a variation of one of these problems through what Soviet mathematicians called “perebor,” which Fortnow translates as “brute-force search.” The question of P versus NP is whether a much faster way exists. So far, the answer is no. Take one of these NP-complete problems, called “k-clique,” which Fortnow explains as follows: “What is the largest clique on Facebook all of are friends with each other?” Obviously, the more users there are on Facebook, the more difficult it is to find the biggest self-enclosed clique. And thus far, no algorithm to efficiently solve the clique problem has been discovered. Or, for that matter, to solve any of its NP-complete siblings, which is why most people do think that P ≠ NP. There are considerations here, too, beyond math. Aaronson, the M.I.T. scientist, wrote a blog post about why he thinks P ≠ NP, providing ten reasons for why this is so. The ninth of these he called “the philosophical argument.” It runs, in part, as follows: “If P = NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in ‘creative leaps,’ no fundamental gap between solving a problem and recognizing the solution once it’s found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss; everyone who could recognize a good investment strategy would be Warren Buffett.” We already check novels for literary qualities; most critics could easily enough put together a list of categories that make a novel great. Imagine, now, if you could write an algorithm to efficiently create verifiably great fiction. It isn’t quite as outlandish as you think: back in 2008, the Russian writer Alexander Prokopovich “wrote” the novel “True Love” by taking seventeen classics that were recombined via computer in seventy-two hours into an entirely new work. As Prokopovich told the St. Petersburg Times, “Today publishing houses use different methods of the fastest possible book creation in this or that style meant for this or that readers’ audience. Our program can help with that work.” He then added a note of caution: “However, the program can never become an author, like Photoshop can never be Raphael.” But if P = NP, then it could only be a matter of time before someone figured out how to create verifiably “great” novels and paintings with mathematical efficiency. Much of Fortnow’s book is spent depicting a world in which P is proven to equal NP, a world of easily computed bliss. He imagines, for example, an oncologist no longer having to struggle with the trial and error of chemotherapy because “we can now examine a person’s DNA as well as the mutated DNA of the cancer cells and develop proteins that will fold in just the right way to effectively starve the cancer cells without causing any problems for the normal cells.” He also whips up a political scandal in which a campaign manager “hired a computer programmer, who downloaded tens of thousands of well-received speeches throughout the decades. The programmer then used algorithm to develop a new speech based on current events”—one that the unwitting public predictably loves. To postulate that P ≠ NP, as Fortnow does, is to allow for a world of mystery, difficulty, and frustration—but also of discovery and inquiry, of pleasures pleasingly delayed. Fortnow concedes the possibility that “it will forever remain one of the true great mysteries of mathematics and science.” Yet Vinay Deolalikar is unlikely the last to attempt a proof, for all of mathematics rests on a fundamental hubris, a belief that we can order what Wallace Stevens calls “a slovenly wilderness.” It is a necessary confidence, yet we are not always rewarded for it. Alexander Nazaryan is on the editorial board of the New York Daily News, where he edits the Page Views book blog. Illustration by Jordan Awan. Correction: It is the Riemann Hypothesis, not the Reimann Hypothesis.
我们继续和大家分享在StackExchange网站上关于“丢番图方程的两难问题”的英语讨论，讨论的焦点和分歧还是集中在NP的定义上，也就是我们博客的主题。 在讨论中，网友们充分表达了以non-deterministic Turing machine定义NP的流行观点（注）： － An equivalent definition of NP is that it consists of all problems that are decidable (not just verifiable) in polynomial time by a non-deterministic Turing machine. NTMs are known to be no more powerful than TMs in the sense that the set of problems decidable by NTMs is identical to the set of problems decidable by TMs, so clearly by this definition there can be no undecidable problems in NP.（这里的NTM指non-deterministic Turing machine，就是我们所说的NDTM） 对此，我们质疑： －Since « deterministic and nondeterministic TMs computing/deciding the same languages », what is the interest to define NP by this nondeterministic TM? and what are differences between NP and P? 讨论还会继续，有兴趣的网友可以详参。 ＊＊＊＊＊＊ David Richerby ： Problems in NP are decidable by definition: NP is the class of problems decided by nondeterministic Turing machines. It's easy to prove that this is exactly the same set of problems that have polynomial-length certificates that can be verified in polynomial time. If you're worried that problems in NP might not be decidable, then you've misunderstood something. Yu Li （柳渝）： Yes, I am worried that problems in NP might not be decidable. You talk of the equivalence of the two definitions of NP : NP is the class of problems decided by nondeterministic Turing machines; NP is the class of problems having polynomial-length certificates verified in polynomial time. I doubt this equivalence, because the one is about the existence of algorithm to solve a problem and the other about the existence of solution for a problem. The dilemma about Diophantine Equation may be directly related to this equivalence (see more details of my argument: arxiv.org/abs/1501.01906). Raphael : @DavidRicherby I agree that this does not answer the question, but it clearly attempts to do so. Hence, not an answer flags are not appropriate. Bad/incorrect answers should be downvoted. David Richerby : @Raphael I disagree that it attempts to answer the question. It gives a history of NP and claims that the definition of NP that we use is incorrect. Nowhere does it address the question of why solving Diophantine equations is not in NP. David Richerby : @YuLi The equivalence of the two definitions of NP is so straightforward that it's taught in undergraduate complexity theory classes. I suggest not uploading to ArXiv if you don't understand the basics of the field. Raphael : @DavidRicherby It seems to me that the author thinks it's an answer, so it's an honest effort, however misguided. As I said, I think this is a case for downvoting, not flagging. If you still disagree, please reflag and I'll let the other mods handle it. Yu Li （柳渝）: @Raphael This is not an ordinary question, because it questions about some basic concepts of computational complexity theory, so any simply answer is not sufficient. You should listen at least what the author of the question and others think about my answer, before you judge it as Bad/incorrect answer. Yu Li （柳渝）: @DavidRicherby I know well the equivalence of the two definitions of NP, I just doubt it. The use of NDTM to define NP can be traced to Cook’s famous paper in 1971, where his NDTM is not the actual one as TM with guessing module, but a mix of Oracle with TM. However, Oracle does not « guess » a certificate, but directly « find » a solution (see more details of my argument: arxiv.org/abs/1501.01910). Yu Li （柳渝）: @DavidRicherby You said nowhere does it address the question of why solving Diophantine equations is not in NP. In my opinion, this is a very interesting remark! In other words you are also questioning the definition of NP in terms of the relation between decision problems and NP, … Yu Li （柳渝） : I try to provide more details for my above answer. In fact, this question is a dilemma problem. On one hand, the Diophantine Equation Problem (DEP) is undecidable according to Matiyesevich’s theorem (Matiyesevich’s theorem answers Hilbert's tenth problem, and Turing’s Halting problem answers the generalization of Hilbert's tenth problem, that is, the Entscheidungsproblem); but on the other hand, there isn't any undecidable problem in NP according to the definition of NP (decidable and verifiable). That is to say, either DEP is not in NP, or DEP is in NP. Both of them concern the definition of NP. If DEP is not in NP, that means problems in NP (NDTM＝NonDeterminstic Turing Machine) are decidable and verifiable, that is to say we accept P=NP (NDTM). If DEP is in NP, then NP (NTM＝Non Turing Machine) contains decidable and undecidable, obviously decidable is verifiable, therefore the problem is whether undecidable is verifiable? In fact, that is the famous problem of P vs. NP. Certainly, undecidable is unverifiable, so NP corresponds to NTM (Non Turing Machine) instead of NDTM (NonDeterminstic Turing Machine). Going on the premise of DEP is in NP (NTM), we think that the NP (NTM) is Nondeterministic Problem (undecidable), and the current definition of NP (NDTM, decidable and verifiable) has lost this nondeterminism (undecidable), so we think that it needs to be questioned. David Richerby : No, the undecidability of DEP (Hilbert's tenth problem) wasn't shown until 1970, by Matiyesevich. The Entscheidungsproblem is not Hilbert's tenth problem; concerns the validity of formulae of first-order logic. And, once again, the P vs. NP problem is absolutely not a problem about whether undecidable problems are verifiable. Yu Li （柳渝）: @DavidRicherby Note that the answer given by Ben : « the set of problems decidable by NTMs is identical to the set of problems decidable by TMs ». Just in this sense, I think that the definition of NP confuses P with NP, and it leads to P=NP (NDTM). If this definition needs to be questioned, then other conclusions deduced from this definition, like the equivalence of a deterministic verifier and a non-deterministic decider, need also to be questioned. David Richerby : @YuLi it leads to P=NP (NDTM). I have no idea what you mean by that. Also, I don't see the relevance of pointing out that TMs and NTMs decide the same languages. If they didn't decide the same languages, NTMs would be a completely unreasonable model of computation and it's hard to imagine that we'd care what they can compute in polynomial time. In complexity theory, we're taking a finer-grained view and asking about the computational resources required and the definition of NP doesn't confuse that at all. Yu Li （柳渝）: @DavidRicherby Thanks, I have modified my answer according to your remark in order to clarify the relation of the Entscheidungsproblem and Hilbert's tenth problem. Concerning the question about the current definition of NP, it is difficult to discuss in several words. The objective of my answer is just to evoke some reflexions about this basic topic, … Yu Li （柳渝）: @DavidRicherby Talking about languages decided by some models of computation, it concerns the study of the nature of underlying problems. If NP and P are the same languages, how can we identify out the properties of NP? Do not forge that, quand some problems called « NP » appeared, they were observed to have somethings different from P, … David Richerby : If NP and P are the same languages, then there are no properties of NP that are different from properties of P. But deterministic and nondeterministic TMs computing the same languages does not mean that P and NP are the same. You are very confused about this whole subject; I suggest that you spend some time reading textbooks and acquainting yourself with the basics. I don't have time to keep pointing out your misconceptions. Yu Li （柳渝）: @DavidRicherby In any domain of knowledge, the most basic concepts are usually the simplest, but in the time the most difficult. We really need to return to textbooks, and search the origin of basic concepts. Since « deterministic and nondeterministic TMs computing/deciding the same languages », what is the interest to define NP by this nondeterministic TM? and what are differences between NP and P? If someone is interested, welcome to continue the discussion. 注：网友Ben在他给出的answer中详细阐述了流行的NP定义，参看讨论的完整版： 关于“丢番图方程的两难问题”的英语讨论（1）
Stack Exchange是全球最大的问答网站之一（注），其中的“Computer Science”版面有很多关于算法理论诸问题的讨论，我们加入了其中一个质疑NP流行定义问题的讨论，摘出部分对话与大家分享，希望有兴趣的网友也能参加！这是网址： http://cs.stackexchange.com/questions/1887/why-isnt-this-undecidable-problem-in-np ，和 讨论的完整版： stackExchange1.pdf 此外，我们准备将科学网博客中关于NP的讨论介绍给国际同行，最近也有友人询问博文的英语版，推荐给在美国读计算机理论课程遇到困难的孩子看。所以，我们希望将这里的博文双语化，若有网友能协助一起工作，将感谢不尽！ ＊＊＊＊＊＊ BlueRaja - Danny Pflughoeft提问 ：Why isn't this undecidable problem in NP?（为什么这个不可判定问题不在NP类里？） Clearly there aren't any undecidable problems in NP. However, according to Wikipedia: NP is the set of all decision problems for which the instances where the answer is yes have verifiable in polynomial time by a deterministic Turing machine. A problem is said to be in NP if and only if there exists a verifier for the problem that executes in polynomial time. Now consider the following problem: Given a Diophantine equation, does it have any integer solutions? Given a solution, it's easy to verify in polynomial time that it really is a solution: just plug the numbers into the equation. Thus, the problem is in NP. However, solving this problem is famously known to be undecidable! (Similarly, it seems the halting problem should be in NP, since the yes-solution of this program halts at the N-th step can be verified in N steps.) Obviously there's something wrong with my understanding, but what is it? Yu Li（柳渝） ：We think that the dilemma you raised about Diophantine equation is very significant, because it reveals something abnormal in the current definition of NP : - A problem is said to be in NP if and only if there exists a verifier for the problem that executes in polynomial time. Concerning the definition of NP, it can be traced to the 60’s, where a great number of applicable and significant problems were discovered for which no polynomial algorithms could be found to solve them, in order to recognize these problems from those problems solvable in Polynomial time (P), the concept of NP was put out. However, the current definition of NP as verifiable in polynomial time confuses NP with P, because a problem in P is also verifiable in polynomial time. In another word, such definition leads to the loss of the essence of NP, « nondeterminisme ». Consequently, it causes serious ambiguities in understanding NP, for example, your dilemma : by nature the problem of Diophantine equation is undecidable; but by the definition of NP, it is decidable, … In our opinion, the difficulty in solving « P versus NP » lies firstly at cognition level, so if we hope to get an insight into « P versus NP », we need at first to question : What is NP? David Richerby ：This seems to be an opinion piece about the definition of NP, not an answer to the question. The definition of NP is just fine. It doesn't confuse P with NP; rather, it acknowledges that P is a subset of NP. To me, it would be very unnatural if P were not a subset of NP. NP is a class of problems that can be solved within certain resource bounds. That necessarily includes a whole bunch of easy problems (P) that can be solved without coming close to the limit of the resources available. Yu Li（柳渝） ：P and NP have the common property of « certificate verifiable in polynomial time » , but this property is not the essence of NP. If this property is used to define NP, then P is a subset of NP, and NP has P as its subset (decidable) and itself (undecidable). Therefore, one would wonder whether NP is decidable or undecidable? Just like the above dilemma : whether is Diophantine equation undecidable or decidable? So my answer is to suggest to investigate this dilemma from the view of the definition of NP: verifiable, undecidable is unverifiable！ 注： －维基对Stack Exchange的简介： Stack Exchange是一系列问答网站，每一个网站包含不同领域的问题。这些网站参考Stack Overflow，一个关于程序设计的问答网站，也是Stack Exchange的第一个成员。如同Stack Overflow，这些网站使用声望奖励系统，用户对问题和答案进行投票，并影响用户声望。声望系统使这些网站可以自我控制。 －介绍Stack Exchange缘起的文章：全球最大的问答网站之一，Stack Exchange如何养成（ http://www.huxiu.com/article/112013/1.html ） －分析Stack Exchange成功经验的文章：StackExchange和它的游戏规则（ http://andnot.farbox.com/post/ke-yan-bi-ji/stackexchangehe-ta-de-you-xi-gui-ze ）
流行观点“NP是可计算的”，所持的理由是：“NP存在指数时间算法”。 我们已从计算复杂性理论与可计算性理论相分离的现状、NDTM（nondeterministic Turing machine）与不确定性的关系、对“多项式时间”的误解等角度，解读了此流行观点导致NP的“不确定性消失”，致“P versus NP”成为世纪难题。这里，我们再从“问题”与“实例”的角度进一步解读对“NP存在指数时间算法”的误读： 于“实例”，对应的是“具体机器”层次，NP问题的某些“实例”可由NDTM计算，NDTM被定义为：在计算的每一时刻，进行到下一步骤有“多选择（several possibilities）”（A nondeterministic Turing machine is defined in the expected way. At any point in a computation the machine may proceed according to several possibilities. － Sipser's Introduction to the Theory of computation, p. 152）。NDTM与DTM（deterministic Turing machine）等价： Every nondeterministic Turing machine has an equivalent deterministic Turing machine（Sipser's Introduction to the Theory of computation, p. 152），也就是说，NDTM的本质是“确定性”，即NDTM所表达的“多选择”是“确定性”，而不能代表NP的本质“不确定性”，（见博文： http://blog.sciencenet.cn/blog-2322490-882297.html ）。 然而于“问题”，对应“人”的层次，NP的“不确定性”表现为“不可判定（undecidable）”，换句话说，NP无法由NDTM及任何一种形式方式定义！ 由此可见，于NP，“问题”与“实例”是二个层次完全不同的概念。一般来说，“实例”与“问题”的关系也就是常量与变量、具象与抽象、个别与一般的关系，二者相关并非总是等价的，比如，日常语言中说：保持公共场所卫生“人人有责”，但不说“人类有责”，因“人人有责”与“人类有责”相关但有别。同样，“NP问题实例可计算”，并不能推导出“NP可计算”，换句话说，说“NP存在指数时间算法”，只是指某些问题实例可计算，并不意味着任何一个问题实例都是可计算的。
我们一直在解读，“P versus NP”之所以成为“世纪难题”，失足于NP定义：NP＝Nondeterministic Polynomial time（不确定性多项式时间），遂有流行观念“NP是多项式时间可验证的”，与此相关，还有一个流行观念“NP是可计算的”。这些观念直接导致计算复杂性理论（Computational complexity theory）与可计算性理论（Computability theory）相分离，作为计算复杂性理论基础的NP完备理论（NP－completeness theory），就成了无源之水，无本之木！ 于可计算性理论，按人们一般的理解，顾名思义是研究“可计算性”，即研究哪些问题是可计算的，然而，若追本溯源，可以看到，此理论的目的是通过“可计算性”，研究与之相对的“不可判定性”。“可计算性”概念源于古老的西方哲学问题：思维机械化，其中心议题是设想通过将思维表达成计算，来检验和消除认知错误，正如莱布尼茨所说： － 纠正我们推理的唯一方式是使它们同数学一样准确、明晰，这样我们能一眼看出我们的错误，并且在人们有争执的时候，可以简单的说，让我们计算「calculemus」，而无须进一步的忙乱，就能看出谁是正确的。（The only way to rectify our reasonings is to make them as tangible as those of the Mathematicians, so that we can find our error at a glance, and when there are disputes among persons, we can simply say: Let us calculate , without further ado, to see who is right.） 于20世纪初，希尔伯特正式提出了利用计算机彻底系统解决所有数学问题的计划，其中的希尔伯特第10问题，又称“丢番图方程问题”，即探究求解任意的丢番图方程的算法的存在性。然而，哥德尔几乎在同时提出了“哥德尔不完备定理”，证明了不存在着这样的算法，它能正确回答有关初等数论的全部问题。接着，图灵进一步提出普遍意义上的计算机模型－“图灵机”，严格证明了不存在这样的图灵机，一般性地表达为“判定问题（Decision Problem）”，由此形成了可计算性理论的核心内容。 于20世纪40年代，发明了基于冯·诺伊曼结构的实际计算机，计算机应用广泛开展起来，于实际应用中出现了一些计算困难的问题，“计算复杂性理论”于此创生。一般说来，计算复杂性理论研究“复杂性”，即研究那些计算困难问题的“复杂性”，库克（Cook）于1971年的那篇论文《The Complexity of Theorem Proving Procedures》，引入“Nondeterministic Turing machine（NDTM）”，将那些计算困难的问题定义为NP（Nondeterministic Polynomial time），由于NDTM的本质是图灵机（TM），遂有诸如“NP是多项式时间可验证的”、“NP是可计算的”的流行观念，其相关理论称之“NP完备理论”。 由此可见，原本NP的提出是针对计算困难的问题，与P相对，然而NP的流行观念混淆了NP与P的本质区别，导致NP的本质“不确定性”消失，是有计算复杂性理论与可计算性理论完全脱节，这是造成现有的NP完备理论严重困难的最根本性的原因。
“The most serious mistakes are not being made as a result of wrong answers. The true dangerous thing is asking the wrong question.” ― Peter Drucker 现代管理学之父彼得•德鲁克（Peter Drucker）将要离世的时候，做出一个这样的结论：“在管理决策中最常见的错误，是我们强调寻找正确的答案，而不是正确的问题。”他还说：“最严重的错误，不是回答错误，真正危险的事，是问错了问题。” 此现象不仅仅表现在管理决策中，更见诸于生活中的方方面面，或许可以说，这是人的认知的最大盲点。那么，为什么“问题”如此重要？因为“问题”是认知和行为的原点，围绕着“问题”整个思想才得以展开，也就是说，“问题”界定、打造了我们面对的现实，指引着我们行动的方向。 “P versus NP”之所以成为“世纪难题”，正是失足于“强调寻找正确的答案，而不是提出正确的问题”。 就NP而言，最初提出NP，是欲以其“不确定性”本质，区别于P的“确定性”本质。但是，流行的观念却是：NP＝Nondeterministic Polynomial time，即“不确定性多项式时间”，而此定义是基于“不确定性图灵机（NDTM）”的，由于“不确定性图灵机”与“确定性图灵机（DTM）”等价，故此定义是“确定性”的P，而非“不确定性”的NP，至此，“不确定性”就从流行的NP问题中消失了，人们陷入了“NP＝P？”的悖论，而不能自拔！ 换句话说，将NP定义为“不确定性多项式时间”，意在强调寻找正确的答案，而忽略了提出的问题是否正确。为正本清源，将NP从“算法”层次还原到“问题”层次，我们提出NP的定义：NP＝Nondeterministic Problem，即“不确定性问题”。 我们的这个NP定义，并不是仅仅换一个P的略写词，而是对“不确定性”这个术语的真正意义的确定化过程，本博客目前所介绍的内容，旨在算法理论层次上，理清“可计算性”意义上的“确定性”与“不确定性”的关系。“不确定性”这个概念的内涵，远远超过了算法理论这个层次，但在算法理论这个层次理清这个概念，无疑是最基本和最严格的工作。当然，这样的工作需大家参与、达成共识，这本身就是一项艰巨的集体性工作。 在此意义上，我们或许可以理解Hemaspaandra在介绍Gasarch的2012年“P versus NP”调查时的悲叹（ http://blog.sciencenet.cn/blog-2322490-856768.html ）： － I hope that people in the distant future will look at these four articles to help get a sense of people’s thoughts back in the dark ages when P versus NP had not yet been resolved。 （ 我希望在遥远的未来，当人们读到这四篇文章，可以帮助他们了解，在“P versus NP”还没得到解决的黑暗年代里人们的思想状态）
于博文“点评《紐約客》文，兼答网友（1）（ http://blog.sciencenet.cn/home.php?mod=spaceuid=2322490do=blogid=891584 ）”，我们说：“P versus NP”的难度不在“答问题”，而在“问问题”，即认知层次上。结合“问题”的整体观（ http://blog.sciencenet.cn/home.php?mod=spaceuid=2322490do=blogid=884042 ），我们试着进一步阐释此观点。 从“问题”的整体观出发，“问题”涉及到二个层次： 1，认知层次：认知问题、定义问题（recognizing problem），于此层次，出现了新问题，而新问题还处在模糊不清状态，需要将之从已知的旧问题中辨识出来，故“问问题”。 2，行为层次：解决问题、求解问题（solving problem），于此层次，问题已辨识出来，指前进路上的“障碍”，需克服之，以达到目的，故“答问题”。 “问题”的这二个层次对应于中西文对“问题”的阐释，认知层次高于行为层次，二者是互补的关系。 于“P versus NP”，P是“可计算的”，是已知问题，而NP却是新问题。于是，首先须针对此新问题，“问问题”，即问：NP是什么？目的是将NP从P中分辨出来；然后才是针对分辨出来的NP，“答问题”，即解决：NP＝P？ 于是，我们可以看到，目前“P versus NP”的困境在“定义问题”，而不是“求解问题”，因为NP被定义成“图灵机在多项式时间可验证解的问题”，“可验证的”也是“可计算的”，即此NP本质是P。也就是说，将NP定义为“可验证的问题”，导致了其“不确定性”本质的消失，从而暗中肯定了“NP＝P”，以至于“P versus NP”成为了悖论，乃至“世纪难题”，。。。 不幸的是，人们未意识到“P versus NP”难在“定义问题”：NP是什么？却一直纠结于“求解问题”：NP＝P？，。。。 《紐約客》上的文章不仅是大众的好奇，更是专家的困惑，也正是作者所指出的这个问题在诸“千禧年”难题中的特殊性。
关于“P versus NP”，流行的问法如《紐約客》文中（ http://blog.sciencenet.cn/home.php?mod=spaceuid=2322490do=blogid=891301 ）所述：Does P (problems that we can easily solve) equal NP (problems that we can easily check)? 也就是人们所说的：是否所有可验证的问题都是算法可求解的问题？ 当然人们可以这样提问，而且直觉上人们普遍都能接受：NP ≠ P，如Aaronson的the philosophical argument： －“If P = NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in ‘creative leaps,’ no fundamental gap between solving a problem and recognizing the solution once it’s found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss; everyone who could recognize a good investment strategy would be Warren Buffett.” 但是，几十年来，对“NP ≠ P”这样的认知，人们始终未能进行理性和科学的分析，“P versus NP”遂成为了越来越难解的“世纪难题”。我们的观点是，“P versus NP”流行的问法本身存在着认知偏差，也就是我们在博文中试着反复解读的，NP流行定义存在着认知偏差，即将NP定义为“可验证的问题”，导致了NP的“不确定性”本质消失，从而暗中肯定了“NP＝P”，以至于“P versus NP”成为了悖论，乃至“世纪难题”，。。。 所以，“P versus NP”的难度不在“答问题”，而在“问问题”，即认知层次上。这些需要在讨论中逐步揭示和领悟，也就是说，解读“P versus NP”的工作远未结束，。。。
http://www.newyorker.com/tech/elements/a-most-profound-math-problem May 2, 2013 (The New Yorker) A Most Profound Math Problem By Alexander Nazaryan On August 6, 2010, a computer scientist named Vinay Deolalikar published a paper with a name as concise as it was audacious: “P ≠ NP.” If Deolalikar was right, he had cut one of mathematics’ most tightly tied Gordian knots. In 2000, the P = NP problem was designated by the Clay Mathematics Institute as one of seven Millennium Problems—“important classic questions that have resisted solution for many years”—only one of which has been solved since. (The Poincaré Conjecture was vanquished in 2003 by the reclusive Russian mathematician Grigory Perelman, who refused the attached million-dollar prize.) A few of the Clay problems are long-standing head-scratchers. The Riemann hypothesis, for example, made its debut in 1859. By contrast, P versus NP is relatively young, having been introduced by the University of Toronto mathematical theorist Stephen Cook in 1971, in a paper titled “The complexity of theorem-proving procedures,” though it had been touched upon two decades earlier in a letter by Kurt Gödel, whom David Foster Wallace branded “modern math’s absolute Prince of Darkness.” The question inherent in those three letters is a devilish one: Does P (problems that we can easily solve) equal NP (problems that we can easily check)? Take your e-mail password as an analogy. Its veracity is checked within a nanosecond of your hitting the return key. But for someone to solve your password would probably be a fruitless pursuit, involving a near-infinite number of letter-number permutations—a trial and error lasting centuries upon centuries. Deolalikar was saying, in essence, that there will always be some problems for which we can recognize an answer without being able to quickly find one—intractable problems that lie beyond the grasp of even our most powerful microprocessors, that consign us to a world that will never be quite as easy as some futurists would have us believe. There always will be problems unsolved, answers unknown. If Deolalikar’s audacious proof were to hold, he could not only quit his day job as a researcher for Hewlett-Packard but rightly expect to enter the pantheon as one of the day’s great mathematicians. But such glory was not forthcoming. Computer scientists and mathematicians went at Deolalikar’s proof—which runs to dozens of pages of fixed-point logistics and k-SAT structures and other such goodies—with the ferocity of sharks in the presence of blood. The M.I.T. computational theorist Scott Aaronson (with whom I consulted on this essay’s factual assertions) wrote on his blog, If Vinay Deolalikar is awarded the $1,000,000 Clay Millennium Prize for his proof P≠NP, then I, Scott Aaronson, will personally supplement his prize by the amount of $200,000. It wasn’t long before Deolalikar’s paper was thoroughly discredited, with Dr. Moshe Vardi, a computer-science professor at Rice University, telling the Times, “I think Deolalikar got his 15 minutes of fame.” As Lance Fortnow describes in his new book, “The Golden Ticket: P, NP and the Search for the Impossible,” P versus NP is “one of the great open problems in all of mathematics” not only because it is extremely difficult to solve but because it has such obvious practical applications. It is the dream of total ease, of the confidence that there is an efficient way to calculate nearly everything, “from cures to deadly diseases to the nature of the universe,” even “an algorithmic process to recognize greatness.” So while a solution for the Birch and Swinnerton-Dyer conjecture, another of the Clay Millennium Prize problems, would be an impressive feat, it would have less practical application than definitive proof that anything we are able to quickly check (NP), we can also quickly solve (P). Fortnow’s book—which, yes, takes its name from “Willy Wonka the Chocolate Factory”—bills itself as a primer for the general reader, though you will likely regret not having paid slightly more attention during calculus class. Reading “The Golden Ticket” is sort of like watching a movie in a foreign language without captions. You will miss some things, but not everything. There is some math humor, which is at once amusing, cheesy, and endearing exactly in the way that you think a mathematician’s humor might be amusing, cheesy, and endearing. What Fortnow calls “P” stands for polynomial time, meaning the size of the input raised to a fixed number like two or three. Conversely, exponential time is some number raised to the size of the input. Though polynomial time can be long (say, 50 2 ), it is nothing compared to its exponential opposite (2 50 ). If the first is the Adirondacks, the second is the Himalayas. When solving things, we want to keep them in polynomial time if we still want to have time for lunch. “NP” (nondeterministic polynomial time) is a set of problems we want to solve, of varying degrees of difficulty. Many everyday activities rely on NP problems: modern computer encryption, for example, which involves the prime factors of extremely large numbers. Some forty years ago, Richard Karp, the Berkeley theoretician, first identified twenty-one problems as being “NP-complete,” meaning that they are at least as hard as any other NP problem. The NP-complete problems are a sort of inner sanctum of computational difficulty; solve one and you’ve solved them all, not to mention all the lesser NP problems lurking in the rear. Karp’s foreboding bunch of problems have names like “directed Hamiltonian cycle” and “vertex cover.” Though they are extremely hard to solve, solutions are easy to check. A human may be able to solve a variation of one of these problems through what Soviet mathematicians called “perebor,” which Fortnow translates as “brute-force search.” The question of P versus NP is whether a much faster way exists. So far, the answer is no. Take one of these NP-complete problems, called “k-clique,” which Fortnow explains as follows: “What is the largest clique on Facebook all of are friends with each other?” Obviously, the more users there are on Facebook, the more difficult it is to find the biggest self-enclosed clique. And thus far, no algorithm to efficiently solve the clique problem has been discovered. Or, for that matter, to solve any of its NP-complete siblings, which is why most people do think that P ≠ NP. There are considerations here, too, beyond math. Aaronson, the M.I.T. scientist, wrote a blog post about why he thinks P ≠ NP, providing ten reasons for why this is so. The ninth of these he called “the philosophical argument.” It runs, in part, as follows: “If P = NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in ‘creative leaps,’ no fundamental gap between solving a problem and recognizing the solution once it’s found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss; everyone who could recognize a good investment strategy would be Warren Buffett.” We already check novels for literary qualities; most critics could easily enough put together a list of categories that make a novel great. Imagine, now, if you could write an algorithm to efficiently create verifiably great fiction. It isn’t quite as outlandish as you think: back in 2008, the Russian writer Alexander Prokopovich “wrote” the novel “True Love” by taking seventeen classics that were recombined via computer in seventy-two hours into an entirely new work. As Prokopovich told the St. Petersburg Times, “Today publishing houses use different methods of the fastest possible book creation in this or that style meant for this or that readers’ audience. Our program can help with that work.” He then added a note of caution: “However, the program can never become an author, like Photoshop can never be Raphael.” But if P = NP, then it could only be a matter of time before someone figured out how to create verifiably “great” novels and paintings with mathematical efficiency. Much of Fortnow’s book is spent depicting a world in which P is proven to equal NP, a world of easily computed bliss. He imagines, for example, an oncologist no longer having to struggle with the trial and error of chemotherapy because “we can now examine a person’s DNA as well as the mutated DNA of the cancer cells and develop proteins that will fold in just the right way to effectively starve the cancer cells without causing any problems for the normal cells.” He also whips up a political scandal in which a campaign manager “hired a computer programmer, who downloaded tens of thousands of well-received speeches throughout the decades. The programmer then used algorithm to develop a new speech based on current events”—one that the unwitting public predictably loves. To postulate that P ≠ NP, as Fortnow does, is to allow for a world of mystery, difficulty, and frustration—but also of discovery and inquiry, of pleasures pleasingly delayed. Fortnow concedes the possibility that “it will forever remain one of the true great mysteries of mathematics and science.” Yet Vinay Deolalikar is unlikely the last to attempt a proof, for all of mathematics rests on a fundamental hubris, a belief that we can order what Wallace Stevens calls “a slovenly wilderness.” It is a necessary confidence, yet we are not always rewarded for it. Alexander Nazaryan is on the editorial board of the New York Daily News, where he edits the Page Views book blog. Illustration by Jordan Awan. Correction: It is the Riemann Hypothesis, not the Reimann Hypothesis.
世纪难题“P versus NP”，通俗地讲，P代表计算机易解决的一类问题，NP代表计算机难解决的一类问题，“P versus NP”就是问：NP这类困难的问题到底能否被计算机有效解决（NP＝P）？与此问题相关的研究，就形成了计算复杂性理论。 库克（Cook）1971年的那篇论文《The Complexity of Theorem Proving Procedures》，奠定了计算复杂性理论的基础。一方面，该论文提出了逻辑问题SAT（Boolean satisfiability problem）来表达NP；另一方面，却将“求解”与“验证”混淆，得出了NP二个定义等价： －The two definitions of NP as the class of problems solvable by a nondeterministic Turing machine in polynomial time and the class of problems verifiable by a deterministic Turing machine in polynomial time are equivalent. The proof is described by many textbooks, for example Sipser’s Introduction to the Theory of Computation, section 7.3 （ http://en.wikipedia.org/wiki/NP (complexity) ）。 将“求解”与“验证”混淆，可类比于音乐作曲与音乐欣赏的混淆，即发生了概念偷换，照理说这样的认知错误不难被人们识别，但是NP二个定义等价却被学术界和大众广泛认可，至今不疑，这表明其中隐藏着深层次的认知问题，。。。 这里，我们用中国古代哲学家公孙龙(约公元前320-250)提出的著名的逻辑问题“白马非马”，来帮助解读此认知错误。 一，“白马非马” 1，“白马非马”典故 一天，公孙龙骑着一匹白马要进城，城门的门卫说，“白马是马”，依照规定马不可以进城。于是，公孙龙就开始他的论证 – “白马非马”，最后说服了门卫，骑着他的白马进城去了。 2，“白马非马”论证－《公孙龙·白马论》 『白马非马』，可乎？ 曰：可。 曰：何哉？ 曰：马者，所以命形也；白者所以命色也。命色者非命形也。故曰：『 白马非马』。 曰：有白马不可谓无马也。不可谓无马者，非马也？有白马为有马，白之，非马何也？ 曰：求马，黄、黑马皆可致；求白马，黄、黑马不可致。使白马乃马也，是所求一也。所求一者，白者不异马也。所求不异，如黄、黑马有可有不可，何也？ 可与不可，其相非，明。故黄、黑马一也，而可以应有马，而不可以应有白马，是白马之非马，审矣！ 3，“白马非马”的解读 “白马非马”典故包含了二个命题： －“白马是马”：站在门卫的立场，他只注意⼀般的马类，不管是黄马、黑马、白马都属于⼀般的马类。 －“白马非马”：站在公孙龙的立场，他在马类中还要分别白马类，故“白马非马”指白马类不是马类。 这两个命题各自都是正确的，但两者发生混淆就错了，由于门卫不能坚持自⼰原来的认知立场，附和了公孙龙的逻辑，被绕晕成了糊涂⾍。 二，“白马非马”与“P versus NP” 基于“验证”的NP定义，指面对具体对象，验证其是否为解，其本质是P，故若用“可验证性”来定义NP，就意味着NP＝P，也就是说，“不确定性”从NP中消失了，就相当于混淆了门卫的立场与公孙龙的立场，这二个不同层次。
最近我与一个工作在NP问题实际求解前沿的同事对话： 同事：我认为，如果取消了“不确定性图灵机（NonDeterministic Turing Machine NDTM）”这个概念，把NP定义成“确定性图灵机（Deterministic Turing Machine DTM）”在多项式时间内可验证的问题类，不会影响NP问题的实际求解，对NP完备理论也不会产生影响。 柳渝：此议题涉及到二个层次，NP问题的实际求解和NP问题的理论研究。若取消NDTM，就NP理论而言，人们自然会问诸如此类问题： －为什么所有关于NP 完备 理论的文献和书籍，都要花重要的篇幅讲NDTM？ －若NDTM无用，为什么仍然要将此无用的概念灌输给学子们，混淆他们的认知，让他们越学越晕？ －NP 完备 理论的核心是Cook定理（注），而Cook定理的陈述和证明都是建立在NDTM基础之上的，如果取消了NDTM，如何阐述Cook定理？如何理解NP完备理论？ 注：The original statement of Cook’s theorem was presented in Cook’s paper entitled “The complexity of theorem proving procedures” as: － Theorem 1 If a set S of strings is accepted by some nondeterministic Turing machine within polynomial time, then S is P-reducible to {DNF tautologies}. The main idea of the proof of Theorem 1 was described: －Suppose a nondeterministic Turing machine M accepts a set S of strings within time Q(n), where Q(n) is a polynomial. Given an input w for M, we will construct a propositional formula A(w) in conjunctive normal form (CNF) such that A(w) is satisfiable iff M accepts w. Thus ¬A(w) is easily put in disjunctive normal form (using De Morgans laws), and ¬A(w) is a tautology if and only if w ̸∈ S. Since the whole construction can be carried out in time bounded by a polynomial in | w | (the length of w), the theorem will be proved.
It is in the admission of ignorance and the admission of uncertainty that there is a hope for the continuous motion of human beings in some direction that doesn't get confined, permanently blocked, as it has so many times before in various periods in the history of man. - Richard P. Feynman (1918 – 1988) whatIsCookTheorem.pdf 论文已在 arXiv 发布： http://arxiv.org/abs/1501.01910。
“P versus NP”是计算机领域中一个平凡又不凡的问题。说“平凡”，是因为此问题缘起于探讨有效求解大量的应用问题，诸如：旅行商问题，图染色问题，作业调度问题等等；说“不凡”，是因为此问题是计算机理论的核心问题，又是Clay Mathematics Institute收录的七个千禧年难题之一，虽然学术界已投入了巨大资金和人力，至今却没有实质性的进展。 Bill Gasarch于2002年和2012年（http://www.cs.umd.edu/~gasarch/papers/poll2012.pdf），对100和152计算机理论前沿的研究者，进行了关于“P versus NP”前途的调查，是对该问题现状的很好解读。Hemaspaandra在介绍2012的调查时，悲观地说： －我希望在遥远的未来，人们读到这四篇文章，可以帮助他们了解，在P versus NP还没得到解决的黑暗年代里人们的思想状态。 （ I hope that people in the distant future will look at these four articles to help get a sense of people’s thoughts back in the dark ages when P versus NP had not yet been resolved. ） 我们的“NP理论”工作就是针对此问题的探索，我们认为此问题实际上隐含着一直未被人们重视的认知偏差，以致于成了名副其实的「皇帝的新衣」，我们希望借此工作能引起人们对认知基本问题的重视，以及对中西文化互补性的实践和思考，。。。 文章“什么是NP？－ 解读中国哲学悖论“白马非马（What is NP? - Interpretation of a Chinese paradox white horse is not horse）”，就是我们工作的第一阶段的一个总结，希望与感兴趣的同事切磋交流。此外，这里出现的一些观点、术语等，会与流行的有所不同，以后逐步介绍。
两篇来自 Bruce Friedman的博文 http://labsoftnews.typepad.com/lab_soft_news/2012/08/data-vs-information-the-emr-readability-problem.htmlhttp://labsoftnews.typepad.com/lab_soft_news/2012/08/data-vs-information-the-emr-readability-problem-part-ii.html 其中审视了当前医疗信息结构化所忽略的一些问题，主要是在强调结构化的同时，忽略了对数据的加工、忽略数据的人可读性所能带来的好处。机器和人不一样，各自有各自的特点和需求，如何在二者之间取得一个很好的权衡点，是件不容易的事情，CDA从诞生至今，至少朝着这个方向一直在努力，而且FHIR中也强调了这一特性，值得让人去关注。
ACM通讯上的一篇综述： The Status of the P Versus NP Problem 作者简介: Lance Fortnow Biography Lance Fortnow is a professor of Electrical Engineering and Computer Science at Northwestern University specializing in computational complexity and its applications to economic theory. He also hold a courtesy appointment at the Managerial Economics and Decision Sciences department in the Kellogg Graduate School of Management and an adjoint professorship at the Toyota Technological Institute at Chicago. Fortnow received his Ph.D. in Applied Mathematics at MIT in 1989 under the supervision of Michael Sipser. Before he joined Northwestern in 2008, Fortnow was a professor at the University of Chicago, a senior research scientist at the NEC Research Institute and a one-year visitor at CWI and the University of Amsterdam. Fortnow's research spans computational complexity and its applications, most recently to micro-economic theory. His work on interactive proof systems and time-space lower bounds for satsifability have led to his election as a 2007 ACM Fellow. In addition he was an NSF Presidential Faculty Fellow from 1992-1998 and a Fulbright Scholar to the Netherlands in 1996-97. Among his many activities, Fortnow served as the founding editor-in-chief of the ACM Transaction on Computation Theory , serves as chair of ACM SIGACT and sits on the council of the Computing Community Consortium . He served as chair of the IEEE Conference on Computational Complexity from 2000-2006. Fortnow originated and co-authors the Computational Complexity weblog since 2002, the first major theoretical computer science blog. He has over 1200 followers on Twitter . Fortnow's survey The Status of the P versus NP Problem is CACM's most downloaded article. Fortnow is currently working on a book expanding on that article.
汉语是联合国官方正式使用的 6 种同等有效语言之一。请不要歧视汉语！ Chinese is one of the six equally effective official languages of the United Nations. Not to discriminate against Chinese, please! P对NP：请郝克刚教授等专家指教（一） （ 一般背景知识汇报 ， 无穷化版本下的“P 对 NP” ） 求教心切，由于种种原因，下文里面错误难免。 请您不吝批评与指教！衷心感谢！ 主要相关数学分 支：公理集合论，图论， 概率论 ；以及理论计算机科学。 一、术语的缩写、相关数学知识简介 NDTM （ NTM ）， non-deterministic Turing machine ，非确定型图灵机； DTM （ TM ）， deterministic Turing machine ，确定型图灵机； NPC ， NP-complete ， NP- 完全； NPI ， NP-Intermediate ， NP里 不属于 P 类且不属于 NP- 完全问题，早期指“人们 不知道是属于 P 类还是属于 NP- 完全类，还有待于证明其归属”； CH ， continuum hypothesis ， 连续统假设 ； TSP ， traveling salesman problem ， 旅行推销员问题 ； SAT ， Boolean satisfiability problem, Boolean 逻辑可满足性，是由 Cook 证明的第一个 NPC 问题 。 ZF ， Zermelo–Fraenkel set theory ， 策梅洛 - 弗伦克尔公理系统； ZFC ， Zermelo–Fraenkel set theory with the axiom of choice ，承认选择公理的 策梅洛 - 弗伦克尔公理系统 ； NBG 或 GB ， NBG of Neumann–Gdel–Bernays ， 冯 · 诺伊曼、 P. 贝尔奈斯、 K. 哥德尔 集合论公理系统 。 a ，可数无穷基数； c ，连续统的基数（全体实数集的基数）； f ，全体几何曲线集合的 基数 。 CH 的基本含义： The hypothesis, due to G. Cantor (1878), stating that every infinite subset of the continuum R is either equivalent to the set of natural numbers or to R itself. 目前已知“ 连续统假设在 ZF （或 GB ）中是不可判定的，它即不能被证明，也不能被否证。 ” 换言之，在著名的集合论公理系统中，都不足以解决连续统假设。这正是人们不断地寻求新公理系统的主要原因。人们总希望能找到科学的为大家所能接受的公理系统，并且得以解决著名的未解决的问题。 “ Formal unsolvability is understood in the sense that there does not exist a formal derivation in the Zermelo–Fraenkel system ZF either for the continuum hypothesis or for its negation. ” 阿列夫 Aleph 是个有争议的问题。据说有人认为 阿列夫 2 与连续统的基数相等，还有人认为 阿列夫 可数无穷 仍然小于连续统的基数。所以，我不采用 阿列夫 来研究“ P 对 NP ”，而是采用数学意义更为直观明确的 Cantor 无穷级数第二序列（ a , c , f , h , i , 等等）来表述。在 1997 年《百科知识》、 1999 年《哲学研究》等文章里开始使用。 二、本人相关背景简介 我是一名普通的基础课教师，天生的笨傻。每年能用于真正“科研”的时间，十分有限。为了完成岗位职责，要花去大量的时间。 上帝啊！ 我太累了 ！ 我没有时间 ！ 因此推出“ P 对 NP ”完全证明的个人观点，肯定是十分艰难和缓慢的。 本文博文作为正式的介绍材料之一 。 期待有关专家指导俺修改之！ 1993 年暑假，某天夜里后半夜，想到在“ 有穷情况” 下的 P 和 NP 关系。 这个发现，是以生命为代价换来的！ 大约到 1995 年初，真傻又做出“ 无穷版本” 下的 P 和 NP 关系：是一个著名数学问题的特定解释。 2011 年 3 月，给出概率意义下的有穷直接证明。 本人专业背景简介 我目前是天津大学（ 985 大学）在岗的“ 模式识别与智能系统”和“软件工程” 2 个专业的硕士生导师，工学博 士学位。曾经开设硕士生选修课《人工智能专题》多年，以史忠植先生的《高级人工智能》为主要参考书。 从2002年开始 主讲硕士生选修课《模糊理论及应用》至今。 我 1988 年硕士入学后不久，就听说了“ P 对 NP ”问题。该问题的核心，数次被两位教授重复。一位教授开设硕士生《数据结构与算法》多年，俺跟该教授上过这门课；该教授在 1980 年代，就指导过东欧来天津大学的访问学者。另一位教授在图论方面有较深的造诣，曾经对两个经典问题做出世界最好结果。由于未征求这两位教授的意见，此处只能隐去他们的姓名，以避免可能对他们产生的某种不必的负面影响。 其中的图论教授，数次向我们讲解“ P 对 NP ”的核心，并推荐了名著《 GAREY M R, JOHNSON D S. Computers and Intractability: A Guide to the Theory of NP-Completeness . New York: W. H. Freeman, 1979. 》。我从系资料室（现更名为学院资料室）借阅该书的汉译本 20 余年。由本学院上届领导批准，几年前将该书赠送给我。 感谢这位好心的领导！礼轻情意重！ 因此，“ P 对 NP ”是属于我专业背景的科学问题（数学 - 计算机科学）。 三、 对“ P 对 NP ”核心的个人理解 3.1 “ P 对 NP ”定义的核心 P 是 DTM （确定型图灵机）在多项式时间内的可判定问题类。 这里的“问题类”，常被记为“语言类”。“可判定”是可计算性、计算复杂性里面使用的术语。可判定的一个通俗理解，就是可以求解，可以得到正确的答案。典型的 P 问题，有常见的排序 sorting ，数值矩阵的乘法。 NP 是 DTM （确定型图灵机）在多项式时间内的可验证问题类。 NP 是 NDTM （ NTM ，非确定型图灵机）在多项式时间内的可判定问题类。 DTM 与 NDTM 关系的一个直观解释： 非确定型图灵机是一种能够同时进行多路计算的“并行”的图灵机，并且限制这些并行的图灵机之间不能相互通讯。 A nondeterministic Turing machine is a "parallel" Turing machine that can take many computational paths simultaneously, with the restriction that the parallel Turing machines cannot communicate. 3.2 “ P 对 NP ”的有关主流看法 显然， P 包含在 NP 里面。是否所有的 P 都是 NP ，是“ P 对 NP ”的表述方式之一。 NP 里面最难的称为 NPC （ NP 完备的）。 NP 里面的任何问题，都可以在多项式时间内归约为 NPC 。 如果 NPC 找到了多项式时间求解算法，则证明 P=NP 。 如果证明 NPC 必须使用指数时间，则证明 P ¹ NP （ P 不等于 NP，也有人记为 P ！ =NP ）。 如果 P ¹ NP ，则可能存在“不是 P ，又不是 NPC ”的中间类型 NPI 。找到一个 NPI ，则等效于证明 P ¹ NP 。 NPC 的例子很多。第一个 NPC 是 SAT ，常见的自然问题有 TSP 等。 到目前为止，“ P 对 NP ”未见主流承认的答案。 Clearly, is contained in . However , it is not known whether or not the containment is proper . The problem of whether or not equals ( ?) can justly be called the most celebrated open problem in the theory of computation. The significance of this question is due to the fact that many practically important problems are known to be in , whereas it is not known whether or not they are in . In fact, all known deterministic algorithms for these problems are exponential as far as time is concerned. Thus, a proof of would make all of these problems tractable. Most exponential time algorithms are marely variations on exhaustive search, whereas polynomial time algorithms generally are possible only through the gain of some deeper insight into the structure of a problem. 大多数指数时间算法只是穷举搜索的变种，而多项式时间算法通常只有在对问题的结构有了某些比较深入的理解之后才有可能给出。 现有的研究与证明方法主要有三大类：对角化 diagonalization 、电路复杂性 circuit complexity 、证明复杂性 proof complexity 。但国际学术界普遍的看法是这些方法都不能得到彻底的结果。一般认为，“不同数学领域的意外结合”、“ P 或 NP 新特征的使用”、“新的电路复杂性下界证明方法”以及“对角化的新变形”等是可能获得新结果的途径。 3.3 对“ P 对 NP ”的一些个人看法 由于“重复发表”、“首次发表”等现行科技规范问题，这里只能就我的某些看法想有关老师汇报。其余的看法，希望能在“有同行评审的期刊”发表。敬请您的指教！ （ 1 ）“ P 对 NP ”的难度（为什么该问题如此难？） ① 由 NP 定义可知“对于 NDTM ， P=NP ”，因此 “对于 DTM ， P ¹ NP ”才是研究的重点 。这十分类似希尔伯特第四问题，“ P 对 NP ”问题描述的不确定性，误导了人们的研究。造成了 “ P 对 NP ”研究额外的困难性。 缺少对 DTM 和 NDTM 结构差异的充分使用，是导致“ 对于 DTM ， P ¹ NP ”长期缺乏明确结论的原因之一。 ② 目前的以及历史上出现的各种主流研究方法，都集中在 P 或 NP 问题类的数量性质研究上。 从问题类角度看，由于 NPC 类、 P 类只是在 DTM 上计算“速度”的差异，只是一种“量”的区分，而不像“可计算性”是一种质的区分，这是引起 “ P 对 NP ”困难性的 原因之二。因为证明所采用的“逻辑”，通常是成立、不成立两种明确状态（质）划分的。 ③ 如果能证明对于 DTM ， P 不等于 NP ，则无穷版本下的 NPI 就是 Cantor 原本意义下连续统假设的关系。预计可以得出不接受连续统假设的结论。 （ 2 ）“ P 对 NP ”完全证明的结论 “ P 对 NP ”实际上是三个更具体问题的合成： ① 在 NDTM 中 P 等于 NP ； For a NDTM, P=NP; ② 在 DTM 中 P 不等于 NP ； For a DTM, P ¹ NP; ③ 没有关于所采用的理论计算机模型的必要说明，则具有独立性。 从形式语言的表示看， 郝克刚 老师《纠正对 NP 问题的错误理解（ 3 ） -- 对一位网友文章的评论》（ http://blog.sciencenet.cn/home.php?mod=spaceuid=506146do=blogid=530828 ） 表述是很准确的。 这里仍然采用“ 没有 …… 必要说明 ”，基本意图是想提供多的信息：命题对公理系统的独立性，除了该命题对证明所采用的公理系统“独立”外（直观“独立”的意思），公理系统的信息量不够，也可能造成独立。例如实系数一元二次方程，当根的判别式小于 0 时，在实数域是没有解的。这是由公理系统信息量不够引起独立的直观类比或解释。 参见 1974 年的 Chaitin 定理。一般认为， Chaitin 的三条定理，是对 Kurt Friedrich Gdel 的 哥德尔 第一不完全定理（ Gdel's first incompleteness theorem ）的信息论意义下的具体化 。（ Gdel incompleteness theorem 在《苏联数学百科全书 Encyclopedia of Mathematics》扩展版， http://www.encyclopediaofmath.org/index.php/G%C3%B6del_incompleteness_theorem 。 Kurt Gdel 在《Stanford Encyclopedia of Philosophy》， http://plato.stanford.edu/entries/goedel/ ） （ 3 ）“ P 对 NP ”完全证明结论的三类证明 ① 有穷形式下形转化的直接证明； ② 无穷形式 / 版本下的证明，直接否证 Cantor 原本意义下的“连续统假设”； ③ 概率形式、有穷形式下的直接证明。 其中“ ③ 概率形式、有穷形式下的直接证明”，还未公开过。计划争取英文文章。 在 2011 年初夏，以文字形式，向党组织汇报过（党员创优活动的汇报，一个笔记本。 恳请党组织保留该笔记本一些时间 ，感谢党的指导与关怀！） 。 上面的“ ① 有穷形式下形转化的直接证明； ② 无穷形式 / 版本下的证明，直接否证 Cantor 原本意义下的‘连续统假设’”， 1995 年以《 从 NP 结构到超级计算机分类理论》为题目，在天津大学百年校庆研究生院研究生学术报告会（1 995 年 10 月初）公开讲解过。可惜没有录音或录像，希望有人愿意证明我讲过。 “ ① 有穷形式下形转化的直接证明”的细节，计划争取英文文章。 因此，本博文主要汇报“ ② 无穷形式 / 版本下的证明，直接否证 Cantor 原本意义下的‘连续统假设’”。 （ 4 ）无穷形式 / 版本下的证明，直接否证 Cantor 原本意义下的“连续统假设” 该证明发表在 2011 年 TTU 的《 A non-canonical example to support that P is not equal to NP 》，其核心在 2008 年《 密码学与非确定型图灵机 》里扼要介绍过。 “无穷形式 / 版本”的基本意思，是将 DTM 、 NDTM 的运行时间取为无穷大（可数无穷步。接受“实无穷”，令字母表、状态数为可数无穷即可，这很自然；坚定的“潜无穷”论者可能提出怀疑。）。 DTM 此时只有一个新状态、一共生成 a 个状态；而 NDTM 此时产生 | Q-F | a 新状态，以及指数界数目的总状态。 直观地说：限制 NDTM 的转移函数每次只产生一个转移状态，则该最小的 NDTM 就退化为一个 DTM 。所以，容易证明， DTM 至多用指数时间就可以模拟一个对应的 NDTM 。这等价于“ P 包含在 NP 里面”。 如果证明“ DTM 必须用指数时间就才能模拟一个对应的 NDTM ”，则从某种意义上讲，就等价地证明的“ P 不等于 NP ”。而这并不容易，所以 2011 年 TTU 的文章采用“支持 P 不等于 NP ”的说法（ A non-canonical example to support that P is not equal to NP ）。 演绎证明的实质，是将“公理”包含的信息，以某种方式显示出来，所以“演绎证明的结论是前提蕴含的”。假如不是前提蕴含的，就是“独立的”。 假如找到 NPI ，则在其无穷化版本下，等价于否证 Cantor 原本意义下的连续统假设。 目前众所周知的康托三分集（ Cantor ternary set ），显然与连续统假设（ continuum hypothesis ）的研究有直接的关系。 （ 5 ）关于“ P 对 NP ”的独立性 ① 如果没有明确是用 DTM 或 NDTM 求解，则 “ P 对 NP ” 具有独立性。 这是说 “ P 对 NP ”对“用 DTM 或 NDTM 求解 ”独立，而不是对现有的公理集合论系统（ ZF、NGB 等 ）独立 。 这类似：实系数一元二次方程，当根的判别式小于 0 时，在实数域无解；在复数域有解。 又如， 1975 年 Baker 、 Gill 和 Solovay 报道的“存在不同的计算模型 A 、 B ，使得 P A =NP A 、 P B ¹ NP B 分别成立。” ② 承认“对 DTM ， P 不等于 NP ”，则 无穷版本下的 NPI ，就是的 Cantor 原本意义下的连续统假设 CH 。 无穷版本下 NPI 的存在性，对 目前现有的公理集合论系统（ ZF、NBG 等 ）独立。 所以 1975 年 Ladner 证明“如果 P ¹ NP ，则 NPI=(NP - P) 不是空集”以及 1993 年 Zimand 证明如果 NP - P 不空则很大（ If not empty, NP - P is topologically large ），都不能给出确定的结果。 假如 P 不等于 NP ，则 NPI 对应一种介于多项式和指数之间的时间增长方式。由于 Cantor 没有构造出这样的增长方式，所以才在 1878 年提出连续统假设：连续统子集的基数，要么是自然数，要么还是连续统的基数。康托三分集的基数还是连续统的基数 c ；可以从连续线段中抽取有穷或无穷个离散点（自然数集的基数，有穷基数，或可数无穷基数 a ）。 四、请教 4.1 关于 真傻 的叙述 （ 1 ）以上关于无穷化版本下的“ P 对 NP ”问题的看法是否介绍清楚？ （ 2 ）关于“ P 对 NP ”问题难度的解释，《 A non-ca nonical example to support that P is not equal to N P 》的介绍是否清楚？ 4.2 创新性小结与说明 我的方法基本没有创新：属于“不同数学领域的意外结合”和“P或NP新特征的使用”，并没有超出主流的预期。 主要创新： （1）提出“完全证明Full proof”作为数学证明的新标准； （2）建立无穷版本下的NPI与Cantor原本意义下连续统假设的关系。 其它的都是主流预期的，没什么让人耳目一新的。惭愧！ 4.3 有关的问题请教 （ 1 ） “ 2TSP 是 P ， 3TSP 是 NPC ”的证明，还有在 SCI、EI 期刊发表的可能性吗？ （ 2 ） “ P 对 NP ”相关问题对 ZF 的独立性，是否有进一步研究的必要和可能？ 真诚期待有关专家的批评与指教。 衷心感谢！ 主要参考文献： COOK S. The P versus NP Problem, official problem description , . http://www.claymath.org/millennium/P_vs_NP/pvsnp.pdf ALLENDER E. A status report on the P Versus NP question . Advances in Computers , 2009, 77: 117-147. FORTNOW L. The Status of the P versus NP Problem . Communications of the ACM , 2009, 52(9): 78-86. SIPSER M. The history and status of the P versus NP question . Proceedings of the 24th Annual ACM Symposium on the theory of Computing’ 92 (Canada) , 1992, pp 603–618. COOK S. The importance of the P versus NP question . Journal of the ACM , 2003, (50)1: 27-29. HAZEWINKEL M. Encyclopaedia of mathematics: an updated and annotated translation of the Soviet “Mathematical encyclopaedia” . Dordrecht: Kluwer Academic Publishers, 2001. HOPCROFT J E, MOTWANI R M, ULLMAN J D. Introduction to automata theory, languages, and computation (Third edition) . New Jersey: Ad dison Wesley , 2006. GAREY M R, JOHNSON D S. Computers and Intractability: A Guide to the Theory of NP-Completeness . New York : W. H. Freeman, 1979. Nondeterministic Turing Machine . http://mathworld.wolfram.com/NondeterministicTuringMachine.html CHAITIN G J. Information-theoretic computational complexity . IEEE Transactions on Information Theory , 1974, 20(1): 10-15. 中国大百科全书•数学 . 北京 : 中国大百科全书出版社 , 1988. BAKER T, GILL J, SOLOVAY R. Relativizations of the P =? NP question . SIAM Journal on Computing , 1975, 4(4): 431-442. LADNER R E. On the structure of polynomial time reducibility . Journal of the ACM , 1975, 22(1): 155-171. ZIMAND M. If not empty, NP - P is topologically large . Theoretical Computer Science, 1993, 119: 293-310. Weisstein, Eric W. "Nondeterministic Turing Machine." From MathWorld--A Wolfram Web Resource . http://mathworld.wolfram.com/NondeterministicTuringMachine.html 杨正瓴 . 从 NP 结构到超级计算机分类理论 . 天津大学百年校庆研究生院研究生学术报告会（一等奖论文），和天津大学百年校庆自动化系学术报告会， 1995 年 10 月 . 杨正瓴 . 人脑有多复杂？ . 百科知识， 1997 ， 7 （总第 216 期）： pp39 – 40. 杨正瓴 . 人脑复杂性的估计及其哲学意义 ，《中国新时期社会科学成果荟萃》， 1999 ，第 1 卷 p296 。卢继传 主编，中国经济出版社，北京， ISBN 7 – 5017 – 4100 – X/G. 374 ， （第 2 编，哲学，第 4 章，自然辩证法） . 杨正瓴，林孔元 . 人类智能模拟的“第 2 类数学（智能数学）”方法的哲学研究 . 哲学研究， 1999, (4): 44-50. 杨正瓴 . 密码学与非确定型图灵机 . 中国电子科学研究院学报 , 2008, 3(6): 558-562. 杨正瓴 . 第二类计算机构想 . 中国电子科学研究院学报 , 2011, 6(4): 368-374. YANG Zhengl ing ( 杨正瓴 ). A non-canonical example to support that P is not equal to NP . Transactions of Tianjin University, 2011, 17(6): 446-449. 相关链接： 郝克刚 教授《纠正对NP 问题的错误理解（3）-- 对一位网友文章的评论》 http://blog.sciencenet.cn/home.php?mod=spaceuid=506146do=blogid=530828 徐建良 教授《P对NP -- 与杨正瓴老师商榷》 http://blog.sciencenet.cn/./home.php?mod=spaceuid=66861do=blogid=551309 《A FULL PROOF to the P versus NP problem》 http://bbs.sciencenet.cn/home.php?mod=spaceuid=107667do=blogid=486692 里面有一些全文可以下载。 您有兴趣，可以直接跟我要相关的论文全文。 《 “P对NP（P versus NP, P vs NP）”问题的描述、难度、可能的答案》 http://bbs.sciencenet.cn/forum.php?mod=viewthreadtid=266338 《 Vinay Deolalikar宣称自己证明了“P!= NP”（P 不等于 NP）》 http://bbs.sciencenet.cn/forum.php?mod=viewthreadtid=106360
汉语是联合国官方正式使用的6种同等有效语言之一。请不要歧视汉语！ A FULL PROOF to the P versus NP problem “P对NP（P versus NP, P vs NP）”问题的一个“完全证明” 1 相关背景简介 （1）“P对NP（P versus NP, P vs NP）”问题的描述 “ The P versus NP problem is to determine whether every language accepted by some nondeterministic algorithm in polynomial time is also accepted by some (deterministic) algorithm in polynomial time. ” 详见：《“P对NP（P versus NP, P vs NP）”问题的描述、难度、可能的答案》， http://bbs.sciencenet.cn/forum.php?mod=viewthreadtid=266338 以及：《Vinay Deolalikar宣称自己证明了“P!= NP”（P 不等于 NP）》， http://bbs.sciencenet.cn/forum.php?mod=viewthreadtid=106360 The Clay Mathematics Institute 的原始描述： http://www.claymath.org/millennium/P_vs_NP/ . （2）什么是“完全证明” What is a “Full Proof” ？ The Mathematical proofs of a proposition must give the following three cases: (1) The proposition is valid, under some certain axiomatic systems; (2) The proposition is not valid, under other axiomatic systems; (3) The proposition can not be proved/decided, without the necessary designating axiomatic systems. A Full Proof requires that the three cases are all identified definitely. 详见：《什么是“完全的数学证明”？》， http://bbs.sciencenet.cn/forum.php?mod=viewthreadtid=83926 2 未来的可能做法 根据学术规范， 通常情况下，以下重复发表不属于一稿两 ( 多 ) 投： 1) 在专业学术会议上做过口头报告，或者以摘要或会议板报形式报道过的研究结果，但不包括以会议文集或类似出版物形式公开发表过的全文； 2) 对首次发表的内容充实了 x% 以上新数据的学术论文； 3) 有关学术会议或科学发现的新闻报道，但此类报道不应通过附加更多的资料或图表而使内容描述过于详尽； 4) 重要会议的纪要、有关组织达成的共识性文件再次发表； 5) 论文以不同或同一种文字在一种期刊的国际版本上再次发表； 6) 在非英文的本国期刊上发表的属于重大发现的研究论文在国际英文学术期刊再次发表； 7) 在内部资料发表后在公开刊物上再次发表。 本帖主要学术观点，以及《 第二类计算机构想 》等都是汉语的，根据以上规范： 计划将来形成英文的详细论证，再投英文的国际期刊。 3 1995年报告要点回顾 记 DTM 为确定型图灵机（ deterministic Turing machine ）； NDTM 为 “ 非确定型图灵机 ” （ non-deterministic Turing machine ）。 （ 1 ） “P 对 NP” 不能被直接证明。它实际上是 3 个问题的合成： ① 对于 NDTM ， P=NP ； ② 对于 DTM ， P ≠ NP ； ③ “ P 对 NP ” 具 有独立性，如果不指明在那种计算机理论里进行研究。 （ 2 ）对于 DTM ， P ≠ NP ，是通常研究的核心。 从数学研究的整体方法看， “ P 对 NP ” 是属于 “ 数 ” 的范围。既然在 “ 数 ” 的方法下没有获得明确答案，就应该转移到 “ 形 ” 的方法进行研究。 对于第一个 NPC ，即布尔可满足性问题（ Boolean Satisfiability Problem ， SAT ），不难发现，在图论模型下， 2SAT 一定是平面图， 3SAT 以及 4SAT 则可能包含 Kuratowski 图 K 3,3 ，是立体图。而 5SAT 可能包含 Kuratowski 图 K 5 和 K 3,3 ，也是立体图。 （ 3 ）在无穷化版本下， NPI 的存在性，就 是 “ 连续统假设 CH ” ：可数无穷基数 a 和连续统基数 c 之间是否存在一个其它的无穷基数。 4 其后的认识 （ 1 ）用旅行推销员问题（ Travelling Salesman Problem ， TSP ），可以比用 SAT 更直观地说明 “P 对 NP” 的关系。所有顶点度数为 2 的 TSP ，称为 2TSP 。显然， 2TSP 只能是一个回路，或者若干不相交的回路。因此 2TSP 是平面图。相反， 3TSP 或更高的各 TSP ，可能包含与 K 5 或 K 3,3 同胚的子图，不是平面图。 （ 2 ）无穷版本下的 NDTM （非确定型图灵机），可以不是平面图。 计划用英文投稿。 （ 3 ）概率意义下 的 “ 对于 DTM ， P ≠ NP ” ，即 “ 对于 DTM ， P ≠ NP 几乎处处（ almost everywhere ， a. e. ）成立 。 ” 计划用英文投稿。 5 “P对NP”完全证明的要点总结 （1）完全证明的结论 ① 对于 NDTM ， P=NP ； ② 对于 DTM ， P ≠ NP ； ③ “P 对 NP” 具有独立性，如果不指明在那种计算机理论里进行研究。 （2）对DTM，P ≠ NP的3类证明 ① 有穷形式下形转化的直接证明； 2TSP 是平面图。相反， 3TSP 或更高的各 TSP ，可能包含与 K 5 或 K 3,3 同胚的子图，不是平面图。 ② 无穷形式/版本下的证明，直接否证Cantor原本意义下的“连续统假设”； 字母表等为可数无穷时， DTM 仍为可数无穷；相反， NDTM 为连续统。 ③ 概率形式、有穷形式下的直接证明。 暂时不能公开，计划 用英文投稿。 6 相关报告与论文 《 My report and papers on "the P versus NP problem" (P vs NP) 》 http://bbs.sciencenet.cn/home.php?mod=spaceuid=107667do=blogid=483639 从 NP 结构到超级计算机分类理论 . 天津大学百年校庆研究生院研究生学术报告会（一等奖论文） , 和天津大学百年校庆自动化系学术报告会 , 1995 年 10 月 . From the hierarchy of NP to a classification of supercomputer. The Student Academic Symposium of Graduated School to Celebrate the 100th Anniversary of the Founding of Tianjin University, October, 1995. (An oral report in Chinese) 人类智能模拟的 “ 第 2 类数学（智能数学） ” 方法的哲学研究 . 哲学研究, 1999, 4: 44-50. Philosophical research on "the second class mathematics (intelligent mathematics)" for simulations of human intelligence. Philosophical Research, 1999, 4: 44-50. (in Chinese) 密码学与非确定型图灵机 . 中国电子科学研究院学报 , 2008, 3(6): 558-562. Cryptology and non-deterministic Turing machine. Journal of China Academy of Electronics and Information Technology, 2008, 3(6): 558-562. (in Chinese) 第二类计算机构想 . 中国电子科学研究院学报, 2011, 6(4): 368-374. Conception of the second class computer. Journal of China Academy of Electronics and Information Technology, 2011, 6(4): 368-374. (in Chinese) 里面有 1995 年报告（ ）的主要观点概述。 A non-canonical example to support that P is not equal to NP. Transactions of Tianjin University, 2011, 17(6): accepted. 支持 P 不等于 NP 的一个非规范例子（英文稿） . YANG Zhengling (杨正瓴). A non-canonical example to support that P is not equal to NP . Tra nsactions of Tianjin University, 2011, 17(6): 446-449. 现在已经刊出，2011-12-05后记。 “P对NP”难题研究的形转换新思路 ，中科院在线《科学智慧火花》，2011-08-30， http://idea.cas.cn/viewdoc.action?docid=1275 。 ———————————— 附录 ———————————— 《第二类计算机构想. 中国电子科学研究院学报, 2011, 6(4): 368-374》 内容截取如下： 真诚欢迎您的批评！假如上述内容还值得您批评！谢谢！ 该两页内容的图片格式.rar 该两页内容的pdf格式.pdf 2011 A non-canonical example to support P is not equal to NP.pdf 2011 第二类计算机构想 Conception of the Second Class Computer (in Chinese, ZL Yang).pdf 弱弱地问：有木有问题？
My reportand papers on "the P versus NP problem" (P vs NP) 杨正瓴, Zheng-Ling YANG, YANG Zhengling Abbreviations: NDTM, non-deterministic Turing machine; DTM, deterministic Turing machine; NPC, NP-complete; NPI, NP-Intermediate; CH, continuum hypothesis; TSP, traveling salesman problem. The FULL PROOF: The mathematical proofs of a proposition must give the following three cases: (1) The proposition is valid, under some certain axiomatic systems; (2) The proposition is not valid, under other axiomatic systems; (3) The proposition can not be proved/decided, without the necessary designating axiomatic systems. A FULL PROOF requires that the three cases are all identified definitely, because "Any proof is relative, since it is based on certain unprovable assumptions." http://eom.springer.de/P/p075420.htm (Encyclopaedia of Mathematics, Edited by Michiel Hazewinkel, an updated and annotated translation of the Soviet "Mathematical encyclopaedia") The essence of "the P versus NP problem": ① P = NP for a NDTM; ② P ≠NP for a DTM; ③ The “P vs NP problem” can not be proved/decided, without the necessary designating of a NTM or DTM. The keys of two sufficientproofs of "P ≠NP for a DTM": (1) 2SAT is a planar graph; 3SAT can be a non-planar graph, since it can have the Kuratowski graph K3,3. (2) Non-canonically, a maximal NDTM is the power set of DTM. If the "Axiom of power set" in ZFC (Zermelo–Fraenkel set theory with the axiom of choice) is accepted, then P ≠NP for a DTM. My relative report and papers: 从NP结构到超级计算机分类理论 . 天津大学百年校庆研究生院学术报告会（一等奖论文）, 和天津大学百年校庆自动化系学术报告会, 1995年10月. From the hierarchy of NP to a classification of supercomputer. The Student Academic Symposium of Graduated School to Celebrate the 100th Anniversary of the Founding of Tianjin University, October, 1995. (An oral report in Chinese) 人类智能模拟的“第2类数学（智能数学）”方法的哲学研究 . 哲学研究, 1999, 4: 44-50. Philosophical research on "the second class mathematics (intelligent mathematics)" for simulations of human intelligence. Philosophical Research, 1999, 4: 44-50. (in Chinese) 密码学与非确定型图灵机 . 中国电子科学研究院学报, 2008, 3(6): 558-562. Cryptology and non-deterministic turing machine. Journal of China Academy of Electronics and Information Technology, 2008, 3(6): 558-562. (in Chinese) 第二类计算机构想 . 中国电子科学研究院学报, 2011, 6(4): 368-374. Conception of the second class computer. Journal of China Academy of Electronics and Information Technology, 2011, 6(4): 368-374. (in Chinese) A non-canonical example to support that P is not equal to NP . Transactions of Tianjin University, 2011, 17(6): accepted. 支持 P 不等于 NP 的一个非规范例子（英文稿） . YANG Zhengling (杨正瓴). A non-canonical example to support that P is not equal to NP . Tra nsactions of Tianjin University, 2011, 17(6): 446-449. 现在已经刊出，2011-12-05后记。 “P对NP”难题研究的形转换新思路 ，中科院在线《科学智慧火花》，2011-08-30， http://idea.cas.cn/viewdoc.action?docid=1275 。 拟投英文稿2个，正在写作。 相关链接： 真傻 对 “ P 对NP（P versus NP, P vs NP） ”问题的思考，请看： “P对NP（P versus NP, P vs NP）”问题的描述、难度、可能的答案： http://bbs.sciencenet.cn/forum.php?mod=viewthreadtid=266338 Vinay Deolalikar宣称自己证明了“P!= NP”（P 不等于 NP）： http://bbs.sciencenet.cn/forum.php?mod=viewthreadtid=106360
IC50 versus EC50 The IC50 represents the concentration of a drug that is required for 50% inhibition of viral replication in vitro (can be corrected for protein binding etc). The EC50 represents the plasma concentration/AUC required for obtaining 50% of the maximum effect in vivo. http://www.fda.gov/ohrms/dockets/ac/00/slides/3621s1d/tsld036.htm IC50 From Wikipedia, the free encyclopedia Jump to: navigation , search The half maximal inhibitory concentration (IC 50 ) is a measure of the effectiveness of a compound in inhibiting biological or biochemical function. Often, the compound in question is a drug candidate. This quantitative measure indicates how much of a particular drug or other substance ( inhibitor ) is needed to inhibit a given biological process (or component of a process, i.e. an enzyme , cell , cell receptor or microorganism ) by half. In other words, it is the half maximal (50%) inhibitory concentration (IC) of a substance (50% IC, or IC 50 ). It is commonly used as a measure of antagonist drug potency in pharmacological research. Sometimes, it is also converted to the pIC 50 scale (-log IC 50 ), in which higher values indicate exponentially greater potency. According to the FDA , IC 50 represents the concentration of a drug that is required for 50% inhibition in vitro . It is comparable to an EC 50 for agonist drugs . EC 50 also represents the plasma concentration required for obtaining 50% of a maximum effect in vivo . Determination IC 50 of a drug Functional antagonist assay The IC 50 of a drug can be determined by constructing a dose-response curve and examining the effect of different concentrations of antagonist on reversing agonist activity. IC 50 values can be calculated for a given antagonist by determining the concentration needed to inhibit half of the maximum biological response of the agonist. IC 50 values are very dependent on conditions under which they are measured. In general, the higher the concentration of inhibitor, the more agonist activity will be lowered. IC 50 value increases as enzyme concentration increases. Furthermore depending on the type of inhibition other factors may influence IC 50 value; for ATP dependent enzymes IC 50 value has an interdependency with concentration of ATP, especially so if inhibition is all of it competitive . IC 50 values can be used to compare the potency of two antagonists. Competition binding assays In this type of assay, a single concentration of radioligand (usually an agonist) is used in every assay tube. The ligand is used at a low concentration, usually at or below its K d value. The level of specific binding of the radioligand is then determined in the presence of a range of concentrations of other competing non-radioactive compounds (usually antagonists), in order to measure the potency with which they compete for the binding of the radioligand. Competition curves may also be computer-fitted to a logistic function as described under direct fit. In this situation the IC 50 is the concentration of competing ligand which displaces 50% of the specific binding of the radioligand. The IC 50 value is converted to an absolute inhibition constant Ki) using the Cheng-Prusoff equation (see Ki). IC 50 and affinity IC 50 is not a direct indicator of affinity although the two can be related at least for competitive agonists and antagonists by the Cheng-Prusoff eqtn. where Ki is the binding affinity of the inhibitor, IC 50 is the functional strength of the inhibitor, is substrate concentration and km is the affinity of the substrate for the enzyme.Whereas the IC 50 value for a compound may vary between experiments depending on radioligand concentration, the K i is an absolute value. K i is the inhibition constant for a drug; the concentration of competing ligand in a competition assay which would occupy 50% of the receptors if no radioligand were present. Half maximal effective concentration From Wikipedia, the free encyclopedia (Redirected from EC50 ) Jump to: navigation , search The term half maximal effective concentration ( EC 50 ) refers to the concentration of a drug, antibody or toxicant which induces a response halfway between the baseline and maximum after some specified exposure time. It is commonly used as a measure of drug potency and toxicity . The EC 50 of a graded dose response curve therefore represents the concentration of a compound where 50% of its maximal effect is observed . The EC 50 of a quantal dose response curve represents the concentration of a compound where 50% of the population exhibit a response . It is also related to IC 50 which is a measure of a compound's inhibition (50% inhibition). For competition binding assays and functional antagonist assays IC 50 is the most common summary measure of the dose-response curve. For agonist/stimulator assays the most common summary measure is the EC 50 . Concentration measures typically follow a Sigmoidal curve, increasing rapidly over a relatively small change in concentration. The point at which the effectiveness slows with increasing concentration is the IC 50 . This can be determined mathematically by derivation of the best-fit line. However, it is more easily observed from a graph and estimated rather than through complex calculus equations . Equation Many different equations can be used to derive an EC 50 . One possible function is: Y = Bottom + (Top - Bottom)/(1 + (X/EC 50 ) (Hill coefficient) ) where Y is the observed value, Bottom is the lowest observed value, Top is the highest observed value, and the Hill coefficient gives the largest absolute value of the slope of the curve. And an alternate form of the equation is: Y = Bottom + (Top - Bottom)/(1+ 10 ((Log(EC 50 )-X) * (Hill coefficient)) ) Limitations The effects of a stressor or drug generally depend on the exposure time. Therefore, the EC 50 (and similar statistics) will be a function of exposure time. The exact shape of this time function will depend upon the stressor (e.g., the specific toxicant), its mechanism of action, the organism exposed, etcetera. This time dependency hampers the comparison of potency or toxicity between compounds and between different organisms. LC50：半数致死浓度，引起受试对象50%个体死亡的药物浓度。 IC50：半数抑制浓度 ，一种药物能将细胞生长、病毒复制等抑制50%所需的浓度。 EC50：半数效应浓度，引起受试对象50%个体产生一种特定效应的药物剂量。 What is the difference between an IC50 and an EC50 and an ED50? FAQ#1332 The differences are just nomenclature, and not conceptual. EC means effective concentration, and is used for dose-response curves that go up hill. IC means inhibitory concentration, so is used for dose-response curves that go downhill, because the drug inhibits a response. In both cases, C stands for concentration. In some experiments, you vary the administered dose, but don't know the effective concentration. In these cases, the midpoint is called the ED50.
标签: versus
