NP在复杂性和可计算性中的定义是什么？
What's the definition of NP mean in Complexity and Computability?
我们正在学习 CS class 中的复杂性，其中一个主题是 NP 和 P 复杂性。我知道 NP 代表非确定性多项式时间，P 代表多项式时间。现在我正试图理解这些是什么意思。
"Non-deterministic Polynomial"是什么意思？我很确定它与问题的 运行 时间有关，但我不是 100% 确定。我读过维基百科文章和其他一些博客，但他们的解释比我们所做的更高层次，所以如果答案可以 "dumbed down" 一点点。
精简版：如果你有两个问题和解决方案，你可以检查解决方案是否在多项式时间内正确, 它在 NP 中。如果你只有一个问题，你可以找到多项式时间的正确解，它在P中。P是NP的一个子集。
如果你真的想理解它的含义，你需要一些自动机理论的基础知识，并找出什么是确定性和 non-deterministic 图灵机。这可不是什么人能轻易给你看傻的。
我们正在学习 CS class 中的复杂性，其中一个主题是 NP 和 P 复杂性。我知道 NP 代表非确定性多项式时间，P 代表多项式时间。现在我正试图理解这些是什么意思。
"Non-deterministic Polynomial"是什么意思？我很确定它与问题的 运行 时间有关，但我不是 100% 确定。我读过维基百科文章和其他一些博客，但他们的解释比我们所做的更高层次，所以如果答案可以 "dumbed down" 一点点。
精简版：如果你有两个问题和解决方案，你可以检查解决方案是否在多项式时间内正确, 它在 NP 中。如果你只有一个问题，你可以找到多项式时间的正确解，它在P中。P是NP的一个子集。
如果你真的想理解它的含义，你需要一些自动机理论的基础知识，并找出什么是确定性和 non-deterministic 图灵机。这可不是什么人能轻易给你看傻的。