NP - 非确定性多项式时间

Question

我看到了多个NP的定义，有些让我感到困惑，称其为非确定性多项式时间。

“NP是可以在非确定性多项式时间内识别的语言集合。”

我的理解是，常规计算机（没有随机性）无法在多项式时间内识别该语言，但具有某种形式的非确定性（抛硬币？）的计算机可以在多项式时间内解决它？

有人能纠正我吗？您能提供一个抛硬币实际上在多项式时间内解决问题的例子吗，否则这将是指数级的？

我确实理解NP包括可以在多项式时间内验证的语言，但我不明白如何使用非确定性来识别它们。

- Pranav Sodhani

---

https://en.wikipedia.org/wiki/Las_Vegas_algorithm - Mooing Duck

在您的上下文中，认识一种语言意味着什么？ - Nico Schertler

可能是[说一个非确定性图灵机可以在多项式时间内解决NP问题的后果是什么？]的重复问题。(https://dev59.com/5HA65IYBdhLWcg3wogKe) - Matt Timmermans

这不是抛硬币。任何时候，当一个非确定性计算机遇到一个条件时，它会分叉自身，并同时采取两个分支。 - user58697

我的疑虑是，如果它同时经过两个分支，它如何能够在多项式时间内完成它？ - Pranav Sodhani

Answer 1

事实上，硬币翻转涉及到随机性，有些人错误地将非确定性与随机性混淆。假设您有以下问题：

有 n 个门，其中一个门后面有您想要找的奖品。现在，让我们分析不同的方法：

（请注意，为了简化描述，我没有使用大 O 等渐近符号）

确定性算法：一个确定性算法的例子是逐个从左到右打开所有的门；因此，最坏情况下的复杂度是 n 次操作。

随机算法：我抛一枚硬币，如果掷到反面，我会从左到右开始检查门；如果掷到正面，我会从右到左检查门。所以，在期望意义下，我将得到 n/2 次操作。（练习：为什么？）在随机算法中，我们寻求良好的平均（预期）行为。

非确定性算法：非确定性算法是完全不同的故事，这在现实世界中是不可能的。如果你拥有非确定性的力量，在面对多种选择时，你可以同时尝试所有选择。因此，一个非确定性算法可以同时打开所有的 n 个门，用 1 次操作来找到奖品。

现在，以下是可以使用非确定性多项式解决的示例。假设您面前有 2 扇门（在深度为 1 处），您选择其中一个，然后再看到 2 扇门（在深度为 2 处）等等，直到深度 n。因此，实际上在最后一层有 2^n 扇门，其中一个门后面有奖品。

使用确定性方法找到奖品需要 2^n 次操作。但是，使用非确定性，您可以同时打开第一层的两扇门，同时打开第二层的四扇门，以此类推。因此，您可以在 n（非确定性）次操作之后找到奖品。

- A. Mashreghi

Answer 2

在这种情况下，非确定性是指计算模型能够以某种技术意义上“猜测”正确的（执行）路径，从所有可能的执行路径中选择。A. Mashreghi在他的回答中很好地描述了它。

另一种等价的表述NP的方式是，它由那些问题组成，对于这些问题，给定问题实例I和一个“证书”C(I)（可以将其视为算法的提示），我们可以在多项式时间内验证该实例是否有解，其中多项式时间与实例大小和证书大小成正比。（这两种表述之间有一个正式的等价证明。例如，Arora和Barak的书中有详细介绍。）

- blazs