NP - 非确定性多项式时间
NP - Non deterministic polynomial time
我看过 NP 的多种定义，我有点困惑称它为非确定性多项式时间。
"NP is the set of languages that can be recognized in non-deterministic polynomial time."
据我了解，普通计算机（没有随机性）无法在多项式时间内识别语言，但具有某种形式的不确定性（抛硬币？）的计算机可以在多项式时间内解决这个问题？
有人可以纠正我吗？你能给我举个例子吗？抛硬币实际上解决了多项式时间的问题，否则它会是指数级的？
我理解 NP 包括可以在多项式时间内验证的语言的定义，但我不明白如何使用非确定性来识别它们。
事实上，抛硬币是关于随机性的，有些人错误地将non-determinism描述为随机性。假设您遇到以下问题：
有n扇门，其中一扇门后面有你想要找到的奖品。现在，让我们分析一下不同的方法：
（注意为了简化描述我没有使用大O等渐近符号）
确定性：确定性算法的一个例子可以是从左到右一扇一扇地打开所有门；因此，n 个操作的最坏情况复杂度
随机化： 我抛硬币，如果我有尾巴，我会从左到右开始检查门，如果我有正面，我会从右到左检查它们。因此，在预期的意义上，我将获得 n/2 操作。 （练习：为什么？）在随机算法中，我们寻找良好的平均（预期）行为
非确定性：非确定性是一个完全不同的故事，这在现实世界中是不可能的。如果你有不确定性的力量，当面临多种选择时，你可以同时尝试所有的选择。因此，非确定性算法可以同时打开所有 n 扇门；因此需要 1 次操作才能找到奖品。
现在，举一个可以使用不确定性多项式求解的例子。假设您面对 2 扇门（深度 1），您选择一扇，然后您再次看到 2 扇门（深度 2），依此类推，直到深度 n。所以实际上在最后一个深度有2^n扇门，其中一扇门后面有奖品。
使用确定性方法寻找奖品需要 2^n 次操作。但是，使用 non-determinism 可以同时打开深度 1 的两扇门，同时打开 2 层的四扇门，依此类推。因此，您可以在 n（非确定性）操作后找到珍贵的
这种情况下的非确定性是指计算模型在某种技术意义上"guess"从所有可能的执行路径中选择正确（执行）路径的能力。 A. Mashreghi 在他的回答中很好地描述了它。
表征 NP 的一种等效方法是，它由那些问题组成，给定问题的实例 I 和 "certificate" C(I)（其中您可以认为是对算法的提示），我们可以验证实例是否具有实例大小和证书大小的时间多项式解。 （这两个特征之间有等价的正式证明。例如，参见 Arora 和 Barak 的书。）
我看过 NP 的多种定义，我有点困惑称它为非确定性多项式时间。
"NP is the set of languages that can be recognized in non-deterministic polynomial time."
据我了解，普通计算机（没有随机性）无法在多项式时间内识别语言，但具有某种形式的不确定性（抛硬币？）的计算机可以在多项式时间内解决这个问题？
有人可以纠正我吗？你能给我举个例子吗？抛硬币实际上解决了多项式时间的问题，否则它会是指数级的？
我理解 NP 包括可以在多项式时间内验证的语言的定义，但我不明白如何使用非确定性来识别它们。
事实上，抛硬币是关于随机性的，有些人错误地将non-determinism描述为随机性。假设您遇到以下问题：
有n扇门，其中一扇门后面有你想要找到的奖品。现在，让我们分析一下不同的方法：
（注意为了简化描述我没有使用大O等渐近符号）
确定性：确定性算法的一个例子可以是从左到右一扇一扇地打开所有门；因此，n 个操作的最坏情况复杂度
随机化： 我抛硬币，如果我有尾巴，我会从左到右开始检查门，如果我有正面，我会从右到左检查它们。因此，在预期的意义上，我将获得 n/2 操作。 （练习：为什么？）在随机算法中，我们寻找良好的平均（预期）行为
非确定性：非确定性是一个完全不同的故事，这在现实世界中是不可能的。如果你有不确定性的力量，当面临多种选择时，你可以同时尝试所有的选择。因此，非确定性算法可以同时打开所有 n 扇门；因此需要 1 次操作才能找到奖品。
现在，举一个可以使用不确定性多项式求解的例子。假设您面对 2 扇门（深度 1），您选择一扇，然后您再次看到 2 扇门（深度 2），依此类推，直到深度 n。所以实际上在最后一个深度有2^n扇门，其中一扇门后面有奖品。
使用确定性方法寻找奖品需要 2^n 次操作。但是，使用 non-determinism 可以同时打开深度 1 的两扇门，同时打开 2 层的四扇门，依此类推。因此，您可以在 n（非确定性）操作后找到珍贵的
这种情况下的非确定性是指计算模型在某种技术意义上"guess"从所有可能的执行路径中选择正确（执行）路径的能力。 A. Mashreghi 在他的回答中很好地描述了它。
表征 NP 的一种等效方法是，它由那些问题组成，给定问题的实例 I 和 "certificate" C(I)（其中您可以认为是对算法的提示），我们可以验证实例是否具有实例大小和证书大小的时间多项式解。 （这两个特征之间有等价的正式证明。例如，参见 Arora 和 Barak 的书。）