将任何问题拆分为 NP 和 P 的主要意图或主要用途是什么？这是否有任何历史原因，还是他们创造了这些概念来帮助我们？如果是这样，这些对我们有什么帮助？
问问题
116 次
3 回答
2
这是一个过于复杂的问题，无法在这里得到彻底的答案，但简而言之，从实践的角度来看，P 中的问题是可以在合理的时间内找到解决方案的问题，而 NP 中的问题是一个解决方案将花费太多时间来计算（假设 P ！= NP）。
P 和 NP 之间的边界可以非正式地认为是可以和不能使用计算有效解决的问题之间的边界。
您应该首先阅读维基百科http://en.wikipedia.org/wiki/P_versus_NP_problem以了解更多关于这些复杂性类的动机和目的。
于 2011-03-19T18:06:09.687 回答
0
我认为将问题拆分为 P 和 NP 的“实际”意图是下限。如果您证明一个问题是 NP 难的（并且您同意 P != NP 的普遍信念），那么您已经证明您无法找到在合理时间内运行的问题的算法。
更非正式地说，假设你的老板要求你编写一个在 5 分钟内运行的算法。如果你说你找不到，他会认为你在偷懒。如果你向他展示他问你的问题是 NP 难的，他应该确信你做不到。回到形式主义，然后你可以使用近似算法来证明它的合理性。
这都是历史性的对话，因为现在，在行业中，我们有时会实现 NP 完全的问题（例如 SAT 求解器）甚至 PSPACE 完全的问题（例如形式验证，它的大小是 PSPACE 完全的）公式）。另一方面，例如在图形中，您有时无法实现在n^2. 有时甚至nlogn会变得前卫。
于 2011-05-05T17:18:32.820 回答
0
主要思想是根据难度级别划分问题。
这里的P指的是所有简单的问题（可以在合理的时间内解决）。和NP那些困难的。（不存在合理的时间解，但如果你能猜到解，很快就能验证）
将问题分为这两组后，您就可以担心解决问题了。
例如，如果您确实遇到了一个NP问题，您可以意识到它在合理的时间内无法解决并继续前进（或使用良好的猜测并检查解决方案），而不是对解决方案感到头疼。
另一方面，如果它是一个P问题，那么您可能会担心找到更有效的解决方案等等。
于 2017-03-26T09:39:54.727 回答