ACM通信

---

彼得亚雷迪克

2016年2月1日07:14

鉴于这篇文章提到了我是一篇论文[“编辑距离不能计算在强次二次元时间(除非SETH是假的)”，STOC'15]的合著者，我认为我应该做出回应。简而言之，我认为这篇文章中的大部分分析源于媒体报道和实际科学探究之间的混淆。实际上，目前尚不清楚瓦尔迪博士是在处理他所认为的“媒体”现象(记者如何向公众描述科学发展)还是“科学”现象(科学家如何以及为什么在研究中做出和使用假设，并在论文中描述这些假设)。为了避免将这两个问题混为一谈，我将以我们的论文为例逐一阐述。

1)媒体方面:这篇社论的大部分内容都集中在一些描述算法和复杂性方面最新科学发展的新闻报道上。瓦尔迪博士特别提到了《波士顿环球报》一篇报道我们工作的文章的标题(《40年来，计算机科学家一直在寻找一个不存在的解决方案》)。正如我已经在其他地方讨论过的那样(https://liorpachter.wordpress.com/2015/08/14/in-biology-n-does-not-go-to-infinity/#comment-4792)，我完全同意本文的标题和其他部分还有很多需要改进的地方。在众多内容中，结果的条件方面只在文章的最后进行了讨论，因此很容易被忽略。

与此同时，我认为需要一些观点。科学结果的流行报道中的不准确或混淆是一种不幸但普遍且长期存在的现象(例如，参见上世纪70年代关于著名的Khachiyan线性规划算法的新闻报道https://lpsdp.files.wordpress.com/2011/10/ellipsoid-stories.pdf)。原因有很多。也许最主要的原因是媒体和科学家之间的文化差异，记者强调可获得性和新闻价值，而科学家强调准确性。因此，科学报告的简化是必要的，过度简化、不准确或不正确的风险很高。幸运的是，更多的时间和精力花在双方可以导致更彻底和微妙的文章(例如，见https://www.quantamagazine.org/20150929-edit-distance-computational-complexity/)。鉴于大众媒体对算法和复杂性结果的报道越来越多，我相信，假以时日，科学家和记者都将在这个过程中获得宝贵的经验。

2)科学方面:Vardi博士也提出了一些科学观点。特别是:

a) Vardi博士对我们论文的标题持批评态度:“编辑距离不能在强次二次时间内计算(除非SETH为假)。”我只能说，鉴于我们在标题、摘要、引言和论文主体中明确地陈述了假设，我相信标题和论文准确地代表了它的贡献。

b) Vardi博士对SETH的有效性持批评态度，认为它是一个僵硬的假设:这个问题确实是一个强有力的讨论和调查的主题(例如，前面提到的广达杂志的文章)。我和大多数与我讨论过这个问题的人的最佳猜测是，这个假设是正确的。然而，这并不是普遍的观点。量化这个猜想的支持程度将是一个有趣的项目，可能会沿着关于P vs. NP猜想的类似努力的路线(https://www.cs.umd.edu/~gasarch/papers/poll2012.pdf)。在任何情况下，通过依赖较弱的假设或用等价替换单向约简来加强框架是至关重要的;两者都是正在进行的研究对象。然而，即使是现有的发展也已经带来了具体的好处。例如，证明某些问题的条件硬度的失败尝试，导致了那些任务的更好算法。

最后，请允许我指出，这一研究方向的关键动机之一是“确切地”加强复杂性和算法中的理论与实践之间的关系，Vardi博士将这一目标称为一个重要的挑战。具体地说，本研究提供了一个框架来建立证据，证明某些计算问题不能在*具体的*(例如次二次多项式)时间边界内得到解决。总的来说，我相信仔细研究过去十年算法和复杂性的发展会发现，理论和实践之间的差距正在缩小，而不是在扩大。但这是另一个话题了。

注意:此评论将在http://blog.geomblog.org/上交叉张贴。感谢Suresh Venkatasubramanian的热情好客。

---

摩西·瓦迪

2016年2月4日08:05

1.指责媒体夸大科学结果很容易，但这并不完全公平。记者确实从科学界获得信息。例如，虽然这篇文章的标题“编辑距离不能在强次二次元时间内计算(除非SETH为假)”在技术上是准确的，但它传递了与假设标题“SETH隐含编辑距离问题的强二次元下界”截然不同的信息。

2.我没有看到理论和实践之间的差距在缩小，而是在扩大。例如，参见“布尔可满足性:理论与工程”(//www.eqigeno.com/magazines/2014/3/172516-boolean-satisfiability/fulltext)。此外，编辑距离问题的二次下界并不意味着在编辑距离问题的典型实例上存在二次行为。

---

彼得亚雷迪克

2016年2月05日11:51

指责媒体夸大科学结果很容易，但这并不完全公平。记者确实从科学界获得信息。

人们很容易推测信息的流动，而不太了解互动的实际展开方式。仔细阅读这篇文章，应该可以清楚地看出以下几点:(i)结果是有条件的(ii)它基于一个比P<>NP更强大的猜想(iii)对该猜想的支持不是普遍的。在我看来，这篇文章的问题只是表明，考虑到主题的复杂性，双方需要更多的时间和努力来令人满意地传达这些观点。第二次效果更好。

>虽然这篇文章的标题“编辑距离不能在强次二次元时间内计算(除非SETH为假)”在技术上是准确的，但它传递了与假设标题“SETH隐含编辑距离问题的强二次元下界”截然不同的信息。

鉴于建议的改动并不影响上文第(i)..(iii)点，我怀疑会有什么不同。当然，我们都可以推测“如果”的情景。

我没有看到理论和实践之间的差距在缩小，而是在扩大。比如，“布尔可满足性:理论与工程”……

恐怕我不同意这种看法。例如，在组合搜索问题中，有越来越多的工作描述了np困难问题的实例，这些问题可以在亚指数级时间内解决。这包括各种形式的平均案例分析，以及固定参数可跟踪性(FPT)，其目标是识别输入参数，使设计运行时仅在这些参数中呈指数增长的算法成为可能(我知道Vardi博士熟悉这一领域，但为了完整起见，我将此描述包括在内)。这里列出的论文太多了，但是浏览最近的STOC/FOCS/SODA/ICALP进程可以提供很多例子。对于编辑距离及其相关值也有类似的结果。顺便说一句，对CNF-SAT指数硬度的猜测在这些发展中起到了“工具性”的作用，使确定参数化算法的“目标”运行时间成为可能。这表明，对于一般输入的SAT的推测指数硬度和对于特定领域的经验上更快的算法的存在并不矛盾，实际上是相辅相成的。

无论如何，这只是一个例子。其他领域包括海量数据分析、机器学习、云计算等。这样的例子不胜枚举。

---

摩西·瓦迪

2016年2月06日02:37

最近确实有相当数量的工作旨在连接理论和实践，例如，理解SAT求解者在现实世界实例中的良好表现，但恐怕这一工作不会在标准理论会议上发表。在这个方向上的良好工作需要理论和实验的结合，但实验工作并不在理论会议的DNA中。例如，人工智能会议将是一个更好的地方。

---

彼得亚雷迪克

2016年2月06日09:27

我觉得情况没那么糟。以下是我知道的一些最近的参考资料。它们本质上是理论性的，但似乎是相关的。可能还有其他的。

Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, M. S. Ramanujan, Saket Saurabh，
通过小树宽度的后门解决d-SAT。苏打水2015:630 - 641

S. Gaspers和S. Szeider，强大的后门到有界的树宽SAT，
在第54届IEEE年度研讨会上
计算机科学(focus)， IEEE计算机学会，
2013年,489498页。

S. Gaspers和S. Szeider，后门到无环
SAT，第39届国际学术会议论文集
自动机、语言和编程
《计算机科学课堂讲稿》第7391卷。
施普林格，2012,pp. 363374

在任何情况下，我并不是说在这方面理论和实践之间没有差距，或者缩小这一差距不是一个主要的研究挑战(事实上，我确实相信这是一个主要和重要的挑战)。总的来说，我不认为理论和实践之间的差距在扩大。

---

吉尔布

2016年2月16日07:34

在我看来，Arturs Backurs和Piotr Indyk的编辑距离结果也具有相当的实际重要性(对于算法的发展)。在理论方面，该结果和方法没有给无条件证明编辑距离的二次下界带来太大希望(尽管人们可能应该尝试，或寻找为什么这是不可信的原因，参见最后的评论)，如果相信SETH或不相信，可能会有不同的观点，因为它比NP=!P强大得多。但结果*确实*表明，要找到(一般)编辑距离的次二次元算法在实践中是不太可能的。(推翻赛斯的算法遥遥无望，即使有人对此持乐观态度，这也将是推翻赛斯的一种非常奇特的方式。)

当然，练习也有几个层次，你可能会问一些有实际意义的例子，关于不太大的字符串等等。

下面是最后的评论:“几周前，Irit Dinur, Moshe Vardi和我在耶路撒冷讨论了一下这个问题，其中一个问题是，次二次元编辑距离和类似SETH/ sat的问题是否在另一个方向上有减少。

---

摩西·瓦迪

2016年2月17日09:43

我很高兴看到我的社论引起了热烈的交流。另请参阅
Lipton&Regan的https://rjlipton.wordpress.com/2016/02/16/waves-hazards-and-guesses/， Fortnow的http://blog.computationalcomplexity.org/2016/02/the-moral-hazard-of-avoiding-complexity.html和https://www.reddit.com/r/compsci/comments/42r53o/the_moral_hazard_of_complexitytheoretic/。