探索计算本质：P与NP难题解析与复杂理论之旅

5星 · 超过95%的资源需积分: 10 101 浏览量更新于2024-07-18 1 收藏 19.29MB PDF 举报

《自然的计算》是一本深入浅出、富有乐趣的计算机科学著作，作者克里斯托弗·摩尔和斯蒂芬·梅滕斯分别来自新墨西哥大学阿尔伯克基分校和圣达菲研究所，以及奥托·冯·格里克大学马格德堡分校和圣达菲研究所。本书的核心聚焦在计算理论的核心概念上，从P与NP完全性问题的探讨开始，引导读者理解这一基础且具有挑战性的议题。书中首先强调了P与NP问题的重要性，它关乎着计算机科学中的一个重大谜题：是否存在一种算法可以在多项式时间内解决所有其他能在多项式时间内解决的问题（P类）？而NP问题则是那些可能在非多项式时间内解决但目前尚未找到确定解的问题。这个难题的存在使得我们对计算机性能的极限有了深刻的认识，并引发了对算法复杂性的深入研究。接下来，作者带领读者探索了迷宫和游戏中的复杂度，展示了理论优化与实际应用之间的联系。他们讨论了随机算法，包括它们如何通过概率和不确定性来解决复杂问题。互动证明和伪随机性是另一个关键主题，这些概念有助于验证算法的有效性和真实性。书中还涵盖了马尔可夫链和相变理论，这两个概念在统计力学和计算模型中扮演着重要角色，它们揭示了系统行为随参数变化的突然转变。最后，作者触及了量子计算的前沿，探讨其潜在的超越传统计算机的能力，尽管目前仍处于理论探索阶段。《自然的计算》不仅提供了一个理论框架，还通过生动的例子和深入的分析，使读者对计算理论的基础有了直观的理解。无论是对专业学者还是对计算机科学的爱好者来说，这本书都是一次富有启发性的探索之旅，它揭示了计算的本质，以及我们在理解这个世界和设计高效算法上的不懈追求。

Preface

The familiar essayist didn’t speak t o the millions; he spoke to one reader, as if the

two of them were sitting side by side in front of a crackling ﬁre with their cravats

loosened, their favorite stimulants at hand, and a long evening of co nversation

stretching before them. His viewpoint was subjective, his frame of reference

concrete, his style digressive, his eccentricities conspicuous, and his laughter

usually at his own expense. And though he wrote about himself, he also wro te

about a subject, something with which he was so f a miliar, and about which he

was o f ten so enthusiastic, that his words were suffused with a lover’s intimacy.

Anne Fadiman, At Large and At Small

It is not incumbent upon you to ﬁnish the work,

yet neit her are you free to desist from it.

Rabbi Tarfon

The sciences that awe and inspire us deal w ith fundamentals. Biology tries to understand the nature of

life, from its cellular machinery to the gorgeous variety of organisms. Physics seeks the laws of nature on

every scale from the subatomic to the cosmic. These questions are among the things that make life worth

living. Pursuing them is one of the best things humans d o.

The theory of computation is no less fundamental. It tries to understand why, and how, some prob-

lems are easy w hile others are hard. This isn’t a question of how fast our computers are, any more than

astronomy is the study of telescopes. It is a question about the mathematical structures of problems, and

how these structures help us solve problems or frustrate our attempts to do so. This leads us, in turn, to

questions about the nature of mathematical proof, and even of intelligence and creativity.

Computer science can trace its roots back to Euc lid. It emerged through the struggle to build a foun-

dation for mathematics in the early 20th century, and ﬂowered with the advent of electronic computers,

driven partly by the cryptographic efforts of World War II. Since then, it has grown into a rich ﬁeld, full of

deep ideas and compelling questions. Today it stands beside other sciences as one of the lenses we use

to look at the world. Anyone who truly wants to understand how the world w orks ca n no more ignore

computation than they can ignore relativity or evolution.

Computer science is also one of the most ﬂexible and dynamic sciences. New subﬁelds like quantum

computation and phase transitions have prod uced exciting collaborations between computer scientists,

physicists, and mathematicians. When physicists ask what rules govern a quantum system, computer

scientists ask what it can c ompute. When physicists describe the phase transition that turns water to ice,

computer scientists ask whether a similar transition turns prob lems from easy to hard.

xvi PREFACE

This book was born in 2005 when one of us was approached by a publisher to write a book explain-

ing computational complexity to physicists. The tale grew in the telling, until we decided—with some

hubris—to explain it to everyone, including computer scientists. A large part of our motivation was to

write the book we would have liked to read. We fell in love with the theory of computation because of the

beauty and power of its ideas, b ut many textbooks bury these ideas under a mountain of formalism. We

have not hesitated to present material that is technically difﬁcult when it’s appropriate. But at every turn

we have tried to draw a clear distinction between deep ideas on the one hand and technical details on the

other—just as you would when talking to a friend.

Overall, we have endeavored to write our book with the accessibility of Martin Gardner, the playful-

ness of Douglas Hofstadter, and the lyricism of Vladimir Nabokov. We have almost certainly failed on all

three counts. Nevertheless, we hope that the reader will share with us some of the joy and passion we

feel for our adopted ﬁeld. If we have reﬂected, however dimly, some of the radiance that drew us to this

subject, we are content.

We are grateful to many people for their feedback and guidance: Scott Aaronson, Heiko Bauke, Paul

Chapman, Andrew Childs, Aaron Clauset, Varsha Dani, Josep Díaz, Owen Densmore, Irit Dinur, Ehud

Friedgut, Tom Hayes, Robert Hearn, Stefan Helmreich, Reuben Hersh, Shiva Kasiviswanathan, Brian Kar-

rer, David Kempe, Greg Kuperberg, Cormac McCarthy, Sarah Miracle, John F. Moore, Michel Morvan, Larry

Nazareth, Ryan O’Donnell, Mark Olah, Jim Propp, Dana Randall, Sasha Razborov, Omer Reingold, Paul

Rendell, Sara Robinson, Jean-Baptiste Rouquier, Amin Saberi, Jared Saia, Nicolas Schabanel, Cosma Shal-

izi, Thérèse Smith, Darko Stefanovi

c, John Tromp, Vijay Vazirani, Robin Whitty, Lance Williams, Damien

Woods, Jon Yard, Danny Yee, Lenka Zdeborová, Yaojia Zhu, and Katharina Zweig.

For additional comments, we are grateful to Lee Altenberg, László Babai, Nick Baxter, Nirdosh Bhat-

nagar, Marcus Calhoun-Lopez, Timothy Chow, Nathan Collins, Will Courtney, Zheng Cui, Wim van Dam,

Tom D a ngniam, Aaron Denney, Hang Dinh, Taylor Dupuy, Bryan Eastin, Charles Efferson, Veit Elser,

Leigh Fanning, Steve Fla mmia, Matthew Fricke, Michel Goemans, Benjamin Gordon, Stephen Guerin,

Samuel Gutierrez, Russell Ha nson, Jacob Hobbs, Neal Holtschulte, Peter Høyer, Luan Jun, Valentine Ka-

banets, Richard Kenyon, Jeffrey Knockel, Leonid Kontorovich, Maurizio Leo, Phil Lewis, Scott Levy, Chien-

Chi Lo, Jun Luan, Shuang Luan, Sebastian Luther, Jon Machta, Jonathan Mandeville, Bodo Manthey,

Pierre McKenzie, Brian Nelson, ThanhVu Nguyen, Katherine Nystrom, Olumuyiwa Oluwasanmi, Boleszek

Osinski, John Patchett, Robin Pemantle, Yuval Peres, Carlos Riofrio, Tyler Rush, Navin Rustagi, George

Saad, Gary Sandine, Samantha Schwartz, Oleg Semenov, David Sherrington, Jon Sorenson, George Stelle,

Satomi Sugaya, Bert Tanner, Amitabh Trehan, Yamel Torres, Michael Velbaum, Chris Willmore, David Wil-

son, Chris Wood, Ben Ya c kley, Yiming Yang, Rich Younger, Sheng -Yang Wang, Zhan Zhang, and Evgeni

Zlatanov. We apologize for any omissions from this list.

We express our heartfelt thanks to the Santa Fe Institute, without whose hospitality we would have

been unable to complete this work. In particular, the SFI library staff—Margaret Alexander, Tim Taylor,

and Joy LeCuy er—fulﬁ lled literally hund red s of requests for ar tic les and b ooks.

We are g rateful to our ed itor Sönke Ad lung for his patienc e, and to A lison Lees for her c areful c opy-

iting . Mar k New man g a ve us invaluab le help w ith the L

ATEX Memoir c lass, in w hic h this b ook is ty peset,

along w ith insig hts and moral suppor t fr om his ow n b ook-w r iting exper ienc es. A nd thr oug hout the pr o-

c ess, A lex Russell shaped our sense of the ﬁ eld , separating the w heat fr om the c haff and helping us to

decide which topics and results to present to the reader. Some fabulous monsters didn’t make it onto the

ark, but many of those that did are here because he urged us to take them on board.

Finally, we dedicate this book to Tracy Conrad and Doro Frederking. Our partners, our loves, they

have made everything possible.

Cristopher Moore and Stephan Mertens

Santa Fe and Magdeburg, 2012

PREFACE xvii
How to read this book
Outside a dog a book is a man’s best friend.
Inside a do g it’s too dark to read.
Groucho Marx
We recommend reading Chapters 1–7 in linear order, and then picking and choosing from later chapters
and sections as you like. Even the advanced chapters have sections that are accessible to nearly everyone.
For the most part, the only mathematics we assume is linear algebra and some occasional calculus.
We use Fourier analysis and complex numbers in several places, especially Chapter 11 for the PCP Theo-
rem and Chapter 15 on quantum computing. Mathematical techniques that we use throughout the book,
such as asymptotic notation and discrete probability, are discussed in the Appendix. We assume some
minimal familiarity with programming, such as the meaning of for and while loops.
Scattered throughout the text you will ﬁnd Exercises. These are meant to be easy, and to help you
check whether you are following the discussion a t that point. The Problems at the end of each chapter
delve more deeply into the subject, providing examples and ﬂeshing out arguments that w e sketch in the
main text. We have been generous with hints and guideposts in order to make even the more demanding
problems doable.
Every once in a while, you will see a quill symbol in the margin—yes, like that one there. This refers
to a note in the Notes section at the end of the chapter, where you can ﬁnd details, historical discussion,
and references to the literature.
A note to the instructor
We have found that Chapters 1–8, with selections from Chapters 9–11, form a good text for an introductory
graduate course on computational complexity. We and others have successfully used later chapters as
texts or supplementary material for more specialized courses, such as Chapters 12 and 13 for a course
on Markov chains, Chapter 14 for phase transitions, and Chapter 15 for quantum computing. Some old-
fashioned topics, like formal languages and automata, are missing from our book, and this is by design.
The Turing machine has a special place in the history of computation, and we discuss it along with
the λ-calculus and partial recursive functions in Chapter 7. But we decided early on to write about com-
putation as if the Church-Turing thesis were true—in other words, that we are free to use whatever model
of computation makes it easiest to convey the key ideas. Accordingly, w e describe algorithms at a “soft-
ware” level, as programs written in the reader’s favorite programming language. This lets us draw on the
reader’s experience and intuition that programs need time and memory to run. Where necessary, such as
in our discussion of LOGSPACE in Chapter 8, we drill down into the hardware and discuss details such as
our model of memory access.
Please share with us your experiences with the book, as well as any mistakes or deﬁciencies you ﬁnd.
We will mainta in errata at nature-of-computation.org. We can also provide a solution manual on request,
which currently contains solutions for over half the problems.