P与NP澄清

Question

引自维基百科的P vs NP问题,关于算法的时间复杂性"......询问计算机能够快速验证其解决方案的每个问题是否也可以通过计算机快速解决."

我希望有人可以澄清"验证问题"和"解决问题"之间的区别在哪里.

Answer 1

我希望有人可以澄清"验证问题"和"解决问题"之间的区别在哪里.

它不是"验证问题 ",而是"验证解决方案 ".例如,您可以在多项式时间内检查给定集合是否对SAT有效.这样的集合的实际生成是NP难的.维基百科文章NP(复杂性)中基于Verifier的定义部分可以帮助您:

基于验证者的定义

为了解释NP的基于验证者的定义,让我们考虑子集和问题:假设给出了一些整数,例如{-7,-3,-2,5,8},我们希望知道这些整数中的一些是否总和为零.在这个例子中,答案是"是",因为整数的子集{-3,-2,5}对应于和(-3)+( - 2)+ 5 = 0.决定是否这样的任务存在和零的子集称为子集和问题.

随着我们输入算法的整数数量变大,子集的数量呈指数增长,实际上子集和问题是NP完全的.但是,请注意,如果给定一个特定的子集(通常称为证书),我们可以通过仅对子集的整数求和来轻松检查或验证子集和是否为零.因此,如果总和确实为零,则该特定子集是答案为"是"的证据或见证.验证给定子集是否具有零的算法称为验证者.当且仅当存在针对在多项式时间内执行的问题的验证者时,才会在NP中出现问题.在子集和问题的情况下,验证者仅需要多项式时间,因此子集和问题在NP中.

如果你更多地了解图论,那么Hamilton循环就是NP完全问题.检查给定解决方案是否是Hamilton循环(线性复杂度,遍历解决方案路径)是微不足道的,但是如果P!= NP,则不存在解决问题的多项式运行时算法.

在这种情况下,"快速"这个词可能会产生误导.在这方面,算法是快速的,当且仅当它的最坏情况运行时受到多项式函数的限制,例如O(n)或O(n log n).n由于您具有n!不同的排列,因此创建具有长度的给定范围的所有排列不受限制.这意味着问题可以在n ¹⁰⁰ log n中解决,这将花费很长时间,但这仍然被认为是快速的.另一方面,TSP的第一个算法之一是O(n!),另一个是O(n ² 2 ⁿ).与多项式函数相比,这些东西真的非常快速地增长.