问题描述
这维基百科中，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完全问题。这是微不足道的检查给定的解决方案是否是哈密尔顿周期（线性复杂度，遍历解决路径），但是若P！= NP比不存在算法与多项式运行时间解决了这个问题。
也许所谓快是误导在这方面。一种算法是快速在这方面，当且仅当它的最坏情况下的运行时间是多项式函数为界，如 O（N）或 0 （N日志N）。所有排列对于给定的范围内，长度 N 是无界，因为你有 N！不同排列的创建。这意味着问题可以在需要解决的 N 日志N 的，这需要很长的时间，但是这仍然是快速的考虑。而另一方面，对TSP的第一个算法之一是为O（n！），另一种是为O（n 2 ）。而相比于多项式函数这些东西长大真的，真快。
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.
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:
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澄清的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！