“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克莱千禧年奖,那么我,ScottAaronson,将私人补充他
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,000ClayMillenniumPrizeforhisproofP≠NP,thenI,ScottAaronson,willpersonallysupplementhisprizebytheamountof
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 [such that] all of [them] 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 [an] 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.
评论 (0)