P与NP澄清 [英] P versus NP Clarification

问题描述

这维基百科中，P VS NP问题引，对于算法的时间复杂度...询问是否所有问题，其解决方案可由计算机被快速验证也可以通过计算机来迅速解决。

我希望有人可以明确的验证问题和解决问题的区别就在这里什么。

解决方案

  

我希望有人可以明确的验证问题和解决问题的区别就在这里什么。

这不是验证的问题的，但是的验证解决方案的。例如，你可以检查在多项式时间内给定是否有效 SAT 的。实际的生成，一套是NP难。本节<一href="http://en.wikipedia.org/w/index.php?title=NP_%28complexity%29&oldid=562909910#Verifier-based_definition"相对=nofollow> 验证为基础的定义的，在维基百科的文章NP（复杂性）可以帮助你一点点：

  

验证为基础的定义

     

为了解释的验证为基础定义的 NP ，让我们考虑的子集和问题：假设我们给出了一些整数，如{-7，-3，-2， 5,8}，我们想知道是否有些整数总结为零。在这个例子中，答案是是，因为整数的子集{-3，-2，5}对应于决定是否这样一个的总和（-3）+（ - 2）+ 5 = 0的任务用总和为零子存在就是所谓的子集和问题。

     

作为整数我们送入算法变大的数目，子集的数量呈指数增长，而事实上该子集和问题是的 NP -complete。但是，请注意，如果我们有一个特定子集（通常称为证书），我们可以很容易地检查或验证的子集和是否为零，仅通过总结子集的整数。因此，如果总和确实为零，该特定子集是证明或证人的事实，答案是是。一种算法，验证给定子集是否具有零总和被称为验证。一个问题被认为是在<强> NP 当且仅当存在一个验证者为，其执行在多项式时间的问题。在情况下，子集和问题的，验证程序仅需要多项式时间，由于这个原因，子集和问题的是在<强> NP

如果你更进图论的汉密尔顿周期是一个NP完全问题。这是微不足道的检查给定的解决方案是否是哈密尔顿周期（线性复杂度，遍历解决路径），但是若P！= NP比不存在算法与多项式运行时间解决了这个问题。

也许所谓快是误导在这方面。一种算法是快速在这方面，当且仅当它的最坏情况下的运行时间是多项式函数为界，如 O（N）或 0 （N日志N）。所有排列对于给定的范围内，长度 N 是无界，因为你有 N！不同排列的创建。这意味着问题可以在需要解决的 N ¹⁰⁰ 日志N 的，这需要很长的时间，但是这仍然是快速的考虑。而另一方面，对TSP的第一个算法之一是为O（n！），另一种是为O（n ² 2 ^N ）。而相比于多项式函数这些东西长大真的，真快。

Quoted from wikipedia, the P vs NP problem, regarding the time complexity of algorithms "... asks whether every problem whose solution can be quickly verified by a computer can also be quickly solved by a computer."

I am hoping that somebody can clarify what the difference between "verifying the problem" and "solving the problem" is here.

解决方案

I am hoping that somebody can clarify what the difference between "verifying the problem" and "solving the problem" is here.

It's not "verifying the problem", but "verifying the solution". For example you can check in polynomial time whether a given set is valid for SAT. The actual generation of such set is NP hard. The section Verifier-based definition in the Wikipedia article NP (complexity) could help you a little bit:

Verifier-based definition

In order to explain the verifier-based definition of NP, let us consider the subset sum problem: Assume that we are given some integers, such as {−7, −3, −2, 5, 8}, and we wish to know whether some of these integers sum up to zero. In this example, the answer is "yes", since the subset of integers {−3, −2, 5} corresponds to the sum (−3) + (−2) + 5 = 0. The task of deciding whether such a subset with sum zero exists is called the subset sum problem.

As the number of integers that we feed into the algorithm becomes larger, the number of subsets grows exponentially, and in fact the subset sum problem is NP-complete. However, notice that, if we are given a particular subset (often called a certificate), we can easily check or verify whether the subset sum is zero, by just summing up the integers of the subset. So if the sum is indeed zero, that particular subset is the proof or witness for the fact that the answer is "yes". An algorithm that verifies whether a given subset has sum zero is called verifier. A problem is said to be in NP if and only if there exists a verifier for the problem that executes in polynomial time. In case of the subset sum problem, the verifier needs only polynomial time, for which reason the subset sum problem is in NP.

If you're more into graph theory the Hamilton cycle is a NP-complete problem. It's trivial to check whether a given solution is a Hamilton cycle (linear complexity, traverse the solution path), but if P != NP than there exists no algorithm with polynomial runtime which solves the problem.

Maybe the term "quick" is misleading in this context. An algorithm is quick in this regard if and only if it's worst-case runtime is bounded by a polynomial function, such as O(n) or O(n log n). The creation of all permutations for a given range with the length n is not bounded, as you have n! different permutations. This means that the problem could be solved in n ¹⁰⁰ log n, which will take a very long time, but this is still considered fast. On the other hand, one of the first algorithms for TSP was O(n!) and another one was O(n² 2ⁿ). And compared to polynomial functions these things grow really, really fast.

这篇关于P与NP澄清的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！