我已经看到了 NP 的多种定义，我有点困惑将其称为非确定性多项式时间。
“NP 是一组可以在非确定性多项式时间内识别的语言。”
我的理解是，普通计算机(没有随机性)无法在多项式时间内识别语言，但是具有某种形式的不确定性(硬币翻转？)的计算机可以在多项式时间内解决这个问题？
有人可以纠正我吗？你能给我提供一个例子，其中硬币翻转实际上在多项式时间内解决了这个问题，否则这将是指数级的吗？
我确实理解 NP 包括可以在多项式时间内验证的语言的定义，但我不明白如何使用非确定性来识别它们。
最佳答案
事实上，硬币翻转是关于随机性的，有些人 错误地 用随机性来描述非确定性。假设您有以下问题:
有 n 扇门，其中一扇门后面有你想要寻找的奖品。现在，让我们分析不同的方法:
(注意，为了简化描述，我没有使用大 O 等渐近符号)
确定性: 确定性算法的一个例子可以是从左到右一一打开所有门；因此，n 个操作的最坏情况复杂度
随机: 我抛硬币，如果我有尾部，我会从左到右开始检查门，如果我有正面，我会从右到左检查它们。因此，在预期的意义上，我将获得 n/2 次操作。 (练习:为什么？)在随机算法中，我们寻找良好的平均(预期)行为
非确定性: 非确定性是一个完全不同的故事，这在现实世界中是不可能的。如果你有不确定性的力量，当你面临多种选择时，你可以同时尝试所有的选择。因此，非确定性算法可以同时打开所有 n 扇门；因此 1 次操作即可找到奖品。
现在，举一个可以使用不确定性多项式求解的例子。假设您面对 2 扇门(深度 1)，您选择其中一扇门，然后再次看到 2 扇门(深度 2)，依此类推，直到深度 n。所以实际上，在最后一个深度有 2^n 个门，其中一个门后面有一个奖品。
使用确定性方法寻找奖品需要 2^n 次操作。但是，使用非确定性，您可以同时打开深度为 1 的两扇门，同时打开级别 2 的四扇门，依此类推。因此，您可以在 n(非确定性)操作后找到珍贵的
关于algorithm - NP - 非确定性多项式时间，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/40207550/