对于那些只想要调查本身的人来说，不是背部，它在这里。 （注意：部分原因是我在此博客上获得的反馈，它现在将其扩展为121页！）
更新（1月23日）通过请求，我已经准备好了这个P的Kindle友好的版本，但NP Survey-A Mere 260页！
两年前，我了解到约翰纳什 - 约翰纳什 - 与Michail Rassias一起一起编辑了关于数学中伟大的开放问题的体积。他们希望我写下关于P与NP问题的章节 - 一个问题，即纳什自己在1955年送到国家安全局的前言手写信中临近。
一方面，我知道我没有时间进行这样的事业，而且是一个可怕的拖延者，在我写一本书章节的以前的两种情况下，我单独延迟整个卷。但另一方面，约翰纳什。
遵循的是，Michail发给我的一年增加了恐慌电子邮件（然后打电话）通知我，除了我的P与NP的东西除外，整个卷已经准备好了，还有机会在这周结束之前？同时，我正在阅读更多关于Karchmer-Wigderson游戏的论文，证明复杂性，时间/空间权衡，难以捉摸的功能和小型算术电路。如果事实证明，P与NP现在是一个很大的主题。
在它的中间，2015年5月23日，约翰纳什和他的妻子艾丽西亚在新泽西州的速度上丧生，在从机场回来的路上（纳什刚刚在挪威的ABEL奖），他们的出租车司机猛击到护栏。
但是在纳什本人遗憾的时候不会活着看到它，但该卷仍在前进。现在我们有效地尊重纳什的记忆，所以我绝对无法退出。
所以最后，去年2月，经过更多几个月的斗争和延迟，我派了我所拥有的Michail，它正式出现在数学中的开放问题。
但我知道我没有完成：仍然派出我的章节向专家征求意见。我做到了，并且大量的反馈开始浇注，为我创造了更多的工作。到目前为止，鹰派是关于几何复杂性理论（GCT）的一个：由Ketan Mulmuley发起的程序，并通过十几个或更多的数学家进行，旨在使用可怕的阿森纳攻击P与NP和相关问题。来自代数几何和代表理论。专家告诉我，没有不确定的术语，我关于GCT的一部分对此有错误 - 但他们不同意彼此关于我是怎么错的。所以我设法努力让他们开心。
然后我搬到了奥斯汀和其他项目的举动，所以我把整个调查放在一边：一年的汗水撕下厕所。在那之后，Bürgisser，ikenmeyer和Panova证明了一个突破性的“无去”定理，大大改变了GCT计划的前景，而且在我回到调查时对我来说更多。
无论如何，今天，我陷入困境的脚踝，我决定完美的是善良的敌人，而且我应该完成该死的调查并把它放在网上，所以读者可以从中受益游行进步（我们可以希望！）渲染完全过时。
1955年，John Nash向国家安全局发送了一个卓越的信，在寻求建立加密的理论基础 - 他所有人都制定了今天我们称之为P =？NP问题，被认为是科学的一个伟大的开放问题之一。在这里，我在2017年调查了这个问题的地位，为数学家，科学家和工程师的广泛观众。我提出了一个关于它的个人视角，为什么重要的是，为什么它是合理的，猜想P♥NP都是真实的和可证明的，为什么证明它是如此艰难，相关问题的景观，至关重要，所取得的进展在过去的半个世纪来解决这些问题。进展的讨论包括对角化和电路下限;相对，代数和自然证据障碍;最近的Ryan Williams和Ketan Mulmuley的作品，（以不同的方式）提示在不可能性证明和算法之间的二元性。
非常感谢每个反馈帮助改善调查的人。如果您有其他反馈，请随时分享评论部分！我的计划是将下一轮反馈纳入2100，如果不是之前。
更新（1月4日）Bill Gasarch写信告诉我Lazslo Babai发布了一条公告，宣布了他的着名“在Quasipolynomialial Time”中的“图形同构”的索赔。具体而言，Babai表示，由于Harald Helfgott发现的错误，他的图形同构算法实际上在大约2 2 ^ O（√log（n））时间内运行，而不是最初声明的n polylog（n）。这仍然击败了图形同构的最佳的运行时间（即，2 O（√（n log n））），并且由大边距，但不像以前那么大。
我向那些被讲话的人而不是因为QuasioMOMOMIAL索赔，在互联网上过早放大，尽管我的免责声明了。
唉，我自己的经历就教会了我的艰难方式，在互联网上，它就是这样做。没有任何责任。
无论如何，我已经更新了我的p与NP调查以反映了这一新的发展。
另一个更新（1月10日）对于那些错过它的人来说，Babai还有另一个更新说他修复了问题，他的图形同构算法的运行时间恢复为QuasiPolynomial。
更新（1月19日）：这一刻 - 启蒙的暮光之城，人类物种回归暴徒的前夕 - 似乎和任何宣布我的P与NP调查的时间一样好。即，非常感谢给我发出建议的所有建议，我已经实施了几乎所有这些，而且我不寻求额外的建议！
199回应“我的116页调查文章对PS. NP：迟到而不是从不”
艾米说：我确实告诉你关于约翰纳什试图扼杀我的男朋友的故事，不是吗？ （这是我唯一的John Nash Story。）
诺亚斯蒂芬斯 - 大卫威兹说：Page 13的次要拼写错误：“给出可能似乎的东西。”这句话只是以缺少一句话结束。 （或者有一些聪明的笑话还是我错过了这里的东西？）
斯科特说：艾米＃1：很高兴听到这个，希望你喜欢它！如果你不这样做，就不需要忍住。无论你说什么，最糟糕的是，它可能导致你在这里的第二个最昭着的分歧。 😉
不，我不认为你曾经告诉过我你的约翰纳什故事 - 听起来很好。
迈克说：斯科特，我几周前读到了对Nash-Rassias卷的贡献，并印象深刻。现在你告诉我你有一个改进的版本！ :::呼吸呼吸:::::认真地，我必须尽快阅读您的修订调查。在新的一年里对三个人祝福！
迈克说：我很快通过修订调查的第6节撇去，特别是第6.6.6节（嘿）。你的（新的？）关于他们的自然对称组对分类问题的评论很有趣。你能说更多关于这个吗？我现在要闭嘴，因为我是在P'ton（HIC）的酒吧，我拼错了太多了。在您的调查和那里的工作中的勇敢！
斯蒂芬韦纳说：我猜有许多，许多不同的NP-完整的问题，但对我来说，官员/阿克曼的结果来自他们的1978年的纸张，“二元二元的NP-Tress决定问题”总是站出来。找不到他们提到的。
killdash9说：你介意发布这份文件的乳胶源吗？我想用更大的字体大小重新编译它。
Jesse Stern说：我非常喜欢我的第一次阅读早期副本，我会确定我会再次阅读这个版本并利用它的宝贵汇编。感谢所有的辛勤工作！
Taymon A. Beal说：有三个数字标题，但没有实际数据。在渲染过程中是否意外省略了？
Rafee Kamouna说：我对116页和内容印象深刻。但是，当我发现你说“p！= np”证明阐述了“p = np”的令人惊叹的后果，我想知道你为什么确认这一点？！？！
你怎么看待你的读者？他们认为，以一种方式对猜想的正确证明确实统治了另一个？
请告诉我们，因为我继续阅读你纸的前几页。尽管巨大的休克，但我非常感谢您的宝贵时间。
斯科特说：Taymon＃10：你看，这就是为什么我把纸张放在我的博客上，然后在将它提交给Arxiv和ECCC之前。 🙂谢谢 - 明天我会创造这些数字，还是消除对他们的参考。
斯科特说：当我发现你说“p！= np”的证明遏制了“p = np”的令人惊叹的后果，我想知道你为什么确认这一点？！？！
你看的原因是，如果可以证明p∈np（以声好方式），则p = np不是真的。 Rafee Kamouna说：任何数学陈述都可以具有证明和防范。 这是戈德尔不完整定理的直接后果。 戈德尔证明了一个数学系统可以证明自己的一致性，如果它不一致。 显然，P！= NP的正确证明永远无法排除另一个正确的P = NP证明。 这是数学逻辑。 这是一个琐碎的明显观察，你提到的任何调查都没有解决。 你和任何先蜂都没有垄断这个问题。 如果你把它拉到“不平等”，那么他就会推动它：“平等”。 匿名说：你为什么要把它放在同一个地址，其中p与np正式独立？ 曾是？ 你已经破坏了那些提到那篇论文的每个人的链接。 这包括你自己。
PostScript版本已启动，因此它不会永远丢失，但仍然......
斯科特说：Rafee＃17：鉴于对我有限的兴趣（以及我对讨论P vs NP的实际研究）有限的兴趣，但也许值得为其他读者解释：
Gödel的第二个不完整的定理（或技术上，Rosser的改进）表示，一个符合，强大的正规系统无法证明自己的一致性。它没有说它不能一致 - 而且事实上，我们只是在最后一句中假设！可证明和真理之间的区别是哥德尔的整点。如果我们不愿意授予我们的数学推理的基本方法，那么我们似乎缺乏讨论在全部讨论数学的基础，因为你所做的那样，为了吸引哥特的定理本身。当然，这些方法的健全性并不是哥德尔的定理挑战，违背了普遍和额头撞击的误解。
但是有一个更基本的问题，逻辑员称之为明确。即使我们想象出来，让我们说，明天发现了PEANO算术或ZF集理论，仍然是SAT的多项式算法，否则也不会有一个。 （就像那样，要么有一个奇怪的完美数字，要么没有。）麻烦将“只是”是，数学推理的方法是每个人都接受了这一点，这不足以建立哪些。
（事实上，人们应该知道：Gödel本人是一名拱金师，他们不仅相信明确的算法，不仅仅是P与NP等算法的陈述 - 他被正确被认为太不言而喻，需要很多讨论 - 但甚至也是如此，首选的公理和连续假设，这比我进一步。）
波格丹说：非常感谢你的伟大调查！我最近在书中读书，非常愉快。据我所知，这是与本书相比的较新版本？您能否告知哪些部分（GCT除外）明显更新，因此重新阅读它们是有意义的？
斯科特说：我真的注意到一年前有涉及“pnp.pdf”的冲突，但是在持续时间才忘记了这篇文章。我想这是可能发生的事情，当你已经足够长时间才能写作两个调查文件，同样的文件名建议自己。 🙂
尽管如此，由于我不想打破新调查的链接，我没有看到任何解决方案，除了为新的方式提供新的方式。所以我现在把旧调查放在了：
斯科特说：Bogdan＃20：与书中的版本相比，几乎没有任何新的材料 - 大多数是旧材料的澄清和错误修正，以及各种添加的引用。如此确定，如果您想要更好，更新的最新账户，请重新缩写GCT部分，但除此之外，不要指望通过新的见解吹走。
斯科特说：anon＃23：对不起，我可能错过了什么 - 那里的错误是什么？
斯科特说：Taymon＃10：Duhhh，毕竟在TEX文件中存在数字;他们只是出现不起作用，因为我编译了使用pdflatex而不是xelatex编译。他们现在在那里（但调查现在是117页而不是116‰）。再次感谢！
斯科特说：匿名＃26：麻烦的是，当我提醒这个问题时，就新的调查，到PNP.PDF的链接已经过了社交媒体。换句话说，因为我之前的错误，任何我所做的选择都需要打破一些链接。在这种情况下，似乎很明显，更好的选择是打破几个链接到14岁的纸张，而不是新的，大大更大，更加“成熟”的工作。
安倍说：我只简要撇去纸张，但我发现它非常启发，谢谢。
关于部分6.2.1的动机有点困惑。虽然Haken表明，解决方案对鸽子穴问题具有指数下限，但已知一段时间克服了这一点，克服了这一点，以回到鸽子洞问题的多项式尺寸偏见。
我刚刚调查这个现在如此原谅我，如果我有这个错误，但从你的调查中，你链接到Beame和Pitassi，看起来人们难以找到弗雷格系统的任何超级多项式计数器证据。这不是至少经验上暗示的，康复问题可能有短缺吗？
斯科特说：Abe＃29：是的，当然，更强大的证明系统可以为PHP提供多项式尺寸样张。除了其与DPLL算法等的简单性及其联系之外，我认为关心解决方案的主要原因只是它是一个良好的界限技术的良好实验室。即，我们仍然仍然研究恒定深度或单调电路的原因，即使我们知道更多的通用电路是强大的。
此外，通常是猜测仅基于算法的难题（具有Grover的算法以及其他代表规则的例外）的难度，这通常是一个坏主意。关于第3节“无知的”无知的不对称“，直接申请。
匿名说：它是在计算机科学历史上实现的，“步数”不是一种强大的硬度衡量标准，因为它从一台机器模型到下一个机器模型变化太大（从MAC到PC等），以及还依赖于如何编码问题的低级细节。问题的渐近复杂性可以被视为对其硬度的贡献，这是清洁和数学，并幸存在沧桑的沧桑。
这有点切向，但让我用这个报价作为咆哮的机会。
我不是说这不是真的。当然，这是一个完全有效的陈述。我只是认为这个名字是误导性，我不同意通常绘制的“哲学”的含义，更好的硬件计算更快（我回忆起Papadimitriou的教科书，如那样的话）。当您查看定理证明时，您可以看到磁带转换为每个单元格包含有关旧磁带的几个相邻小区状态的信息，然后新机器模拟旧电机。您最终最终可以以更少的步骤执行计算（因为在每个步骤中，机器可以一次访问更多信息，并一次执行几个“旧”步骤），但在每个“新”步骤中执行更多工作因为新机器必须保持磁带上信息的一致性;在物理硬件上，这甚至不需要代表加速。我们刚刚交易了机器本身复杂性的步骤数量。
因此，在我看来，线性加速定理并没有对改进硬件的力量说出任何根本的东西，而是关于我们定义的不足（以及磁带压缩定理更加令人遗憾）。我会抛弃通常的定义时间复杂度（步数）×（1 + log 2（磁带字母大小）+ log 2（机器状态的数量））。这是一个有意义的数字：它是您需要写下“计算记录”的比特数，然后您可以验证正确性（即与机器定义相干）。我不知道这么多关于计算硬件的物理学，但我猜测它也可以用作计算使用的能量的粗略估计（我假设在录音带上翻转一下移动头部采取恒定的能量）。我认为“能源复杂性”可能是一个很好的名字（特别是它让您的思想更接近近乎临近近光机会的“图灵机的答案”）。
类似地，空间复杂性可以重新定义为（小区数）×log 2（磁带字母表的大小）（也可以加上log 2（状态的数量）？），这对应于执行给定计算的存储器数量。
一方面，这可能会使一些东西复杂化，但是，在另一方面，这些定义使得增长率略微较低，并且可能会给我们一些更接近言论的复杂性措施。我很遗憾我还没有时间更深入地调查它们。
John Sidles说：斯科特，最近几周我已经彻底同意你的Shtetl优化的散文和评论 - 科学和政治 - 这将努力努力（对我来说至少）写一个有任何合理概率的评论让您或任何SHTETL优化读者，创造性地，愉快地（我希望）在晚上醒来。
因此，为了在SHTETL优化读者之间引起创意和愉快的觉醒状态，这里是您的调查“第3.1节与设定理论无关的建议的最小扩展/修改？”
......过去的世纪，已经庆祝独立结果，据我所知，所有落入四个五个课程，其中一个人只有其中一个将包含p =的独立性？来自ZF集理论的NP：
（5）Gregory Chaitin的基数争论，它与计算本体学辅音，其中存在过多的任何证据系统的算法，以证明它们没有任何识别P使用NP。彭兰·赖凯恩的AMS书评“探索随机性和不可知和不可知”（2001）的公告批判性地概括 - 虽然是关于楚廷数学世界观的（广泛的）文学和（多元化的）观点。
作为进一步的睡眠消失阅读评论，我想回应Lance Fortnow和Bill Gararch推荐Gideon Lewis-Kraus'最近的纽约时报杂志文章“G
......