致谢

首先感谢Moshe Vardi，是他鼓励我写作，他也是我发表在《ACM通讯》杂志上的“P/NP问题的现状”一文的编辑。这篇文章受欢迎的程度让我萌发了把它扩展成一本科普书的念头。

跟我一块写博客的Bill Gasarch不断鼓励我，并仔细审阅了全书各章的初稿。Alana Lidawer和John、Jim，以及Chris Purtilo也阅读了全书的初稿，并提出了许多宝贵意见。KuanLing Chen、Josh Grochow、Ralph Hansen、Adam Kalinich、David Pennock和Rahul Santhanam分别对本书的部分章节提出了许多宝贵的意见。

Manuel Blum、Steve Cook、David Johnson、Leonid Levin和Albert Meyer分别以其个人独到的视角向我讲述了P/NP问题的早期历史。Alexander Razborov对俄罗斯历史的介绍对我帮助很大。

这本书的写作离不开我的生活圈子。作为计算机科学家，我在工作和生活中会与其他研究人员、学生，以及数不清的人交流，这种交流也让我受益匪浅。在此特别感谢加州大学伯克利分校、麻省理工学院、芝加哥大学、阿姆斯特丹的数学与计算机科学中心、NEC研究院、丰田工业大学芝加哥分校以及西北大学的同行们，与他们真挚而友好的讨论让我获益良多。

另外，我还要特别感谢两个人，他们对我早年P/NP问题观念的形成影响很大：Juris Hartmanis，我在康奈尔大学读本科期间首次从他这里接触到了P和NP，还有Michael Sipser，他是我在加州大学伯克利分校和麻省理工学院的博士学位指导老师和好朋友。

在为第6章的地图填色问题寻找例子时，我在网上寻求了帮助，感谢那些做出回应的人：Chris Bogart、HsienChih Chang、Pálvölgyi Dömötör、David Eppstein、Lukasz Grabowski、Gil Kalai、Charles Martel以及Derrick Stolee。

写作期间，我在西北大学的Robert R. McCormick工程与应用科学学院担任电子工程和计算机科学教授。西北大学十分鼓励向公众传播知识的著书活动。我充分利用了教职的特权，尤其是利用了学校图书馆丰富的资源，包括纸质文献和电子文献。西北大学的教职工是最棒的，我的行政助理Marjorie Reyes对我帮助同样很大。

普林斯顿大学出版社的编辑Vickie Kearn为我提供了悉心的指导，并在著书的各个阶段仔细审阅了手稿，让这本书变得更好。我还想感谢Vickie的助手Quinn Fusting，以及出版社的全体工作人员。

最大的感谢留给我的家人：妻子Marcy、两个女儿Annie和Molly，感谢她们对我的爱与鼓励。