NP和P的问题需要什么？

Question

将任何问题分解为NP和P的主要目的或主要用途是什么？这是否有任何历史原因，或者他们是否创造了这些概念来帮助我们？如果是这样，这些对我们有什么帮助？

Answer 1

这是过于复杂的一个问题，以期望在这里一个完整的答案，但总之，从实践的角度，P中的问题是指那些解决方案可以在时间和问题NP合理的量可以找到那些解决方案需要花费太多时间来计算的（假设P！= NP）。

P与NP之间的边界可以被非正式地认为是能够和不能有效地使用计算解决的问题之间的边界。

你应该通过阅读维基百科http://en.wikipedia.org/wiki/P_versus_NP_problem更多地了解这些复杂类的动机和目的开始。

Answer 2

我认为将问题分解为P和NP的“实际”意图是下界。如果你证明一个问题是NP难的（并且你同意P！= NP这个普遍的观点），你已经证明你找不到在合理的时间内运行的问题的算法。

更非正式的，说你的老板要求你写在5分钟运行算法。如果你说你找不到一个，他会认为你正在懈怠。如果你告诉他他问你的是NP难，他应该确信你不能这样做。回到形式主义，你可以用一个近似算法来证明它的合理性。

这是一个历史对话，因为现在，在行业中，我们有时会实施NP完全问题（例如SAT求解器）或甚至PSPACE完整问题（例如形式验证，即PSPACE完成公式的大小）。另一方面，例如在图形中，您有时无法实现在n^2中运行的算法。即使nlogn有时可能会前卫。

Answer 3

主要想法是根据难度级别分离问题。

这里的P将指所有简单的问题（可在合理的时间内解决）。而NP困难的。 （没有合理的时间解决方案，但如果您能猜出解决方案，可以快速验证它）

一旦您将问题分类到这两组中，那么您可以担心解决问题。

例如，如果您遇到问题，而不是在解决方案上突如其来，您可以意识到它在合理的时间内无法解决并继续前进（或使用良好的猜测工作并检查解决方案）。另一方面，如果是P问题，那么您可能会担心找到更有效的解决方案等等。