NP 中的不确定性到底是什么？
What is nondeterministic in NP exactly?
我正在研究 NP-Completeness，我对 NP 问题的定义有疑问。
Material 说
nondeterministic refers to the fact that a solution can be guessed out
of polynomially many options in O(1) time
这里，polynomially many options in O(1) time是什么意思？
例如，在著名的 3SAT 问题中，选项不是呈指数级增长吗？
（b.c。每个文字可以是 true 或 false，如果有 n 个文字，则选项总数为 2*2*2* ... * 2 = 2^n）
然而，它说3SAT问题是NP问题。证书数量呈指数级增长，怎么会是NP问题？
谢谢
这句话似乎是一种奇怪的措辞方式，但它可能指的是类似于能够在 O(1) 中选择 1 和 n 之间的随机数 - 有 n 种可能性，但只能选择其中之一需要 O(1).
另请参阅：nondeterministic algorithms。
"Nondeterministic polynomial time" 是 NP 的完整定义 - "polynomial time" 很重要 - 你做出的每个决定都可能需要 O(1)，但有很多这样的决定，导致理论上可以在多项式时间内解决，如果你能在每一步都做出正确的选择或同时执行所有选项。
想象一棵高度为 p(n) 的 k 叉树。如果您（随机地）在从根节点的每一步中选择正确的子节点，或者您可以以某种方式同时访问所有路径，则可以在 O(p(n)) 中到达正确的叶子节点。
当然，在实践中，您不能依赖于做出正确的随机选择，也不能拥有无限多的处理器 - 如果您要按顺序访问所有节点，则需要 O(k p(n)).
对于 3SAT，我们可以为每个文字随机选择 true 或 false，这导致我们使用多项式时间算法，如果我们所有的随机选择都是正确的，该算法将产生正确的结果。
我正在研究 NP-Completeness，我对 NP 问题的定义有疑问。
Material 说
nondeterministic refers to the fact that a solution can be guessed out of polynomially many options in O(1) time
这里，polynomially many options in O(1) time是什么意思？
例如，在著名的 3SAT 问题中，选项不是呈指数级增长吗？
（b.c。每个文字可以是 true 或 false，如果有 n 个文字，则选项总数为 2*2*2* ... * 2 = 2^n）
然而，它说3SAT问题是NP问题。证书数量呈指数级增长，怎么会是NP问题？
谢谢
这句话似乎是一种奇怪的措辞方式，但它可能指的是类似于能够在 O(1) 中选择 1 和 n 之间的随机数 - 有 n 种可能性，但只能选择其中之一需要 O(1).
另请参阅：nondeterministic algorithms。
"Nondeterministic polynomial time" 是 NP 的完整定义 - "polynomial time" 很重要 - 你做出的每个决定都可能需要 O(1)，但有很多这样的决定，导致理论上可以在多项式时间内解决，如果你能在每一步都做出正确的选择或同时执行所有选项。
想象一棵高度为 p(n) 的 k 叉树。如果您（随机地）在从根节点的每一步中选择正确的子节点，或者您可以以某种方式同时访问所有路径，则可以在 O(p(n)) 中到达正确的叶子节点。
当然，在实践中，您不能依赖于做出正确的随机选择，也不能拥有无限多的处理器 - 如果您要按顺序访问所有节点，则需要 O(k p(n)).
对于 3SAT，我们可以为每个文字随机选择 true 或 false，这导致我们使用多项式时间算法，如果我们所有的随机选择都是正确的，该算法将产生正确的结果。