这些天我一直在研究 NP 问题、计算复杂性和理论。我相信我终于掌握了图灵机的概念，但我有几个疑问。
我可以接受一个非确定性图灵机有几个选项来处理给定的状态和正在读取的符号，并且它总是会选择最好的选项，如维基百科所述
NTM 如何“知道”它应该采取哪些行动？有两种看待它的方式。一是说机器是“最幸运的猜测者”；如果存在这样的转换，它总是选择最终导致接受状态的转换。另一种是想象机器“分支”成许多副本，每个副本都遵循一个可能的转换。DTM 有一个单一的“计算路径”，而 NTM 有一个“计算树”。如果树的任何分支因“接受”条件而停止，我们就说 NTM 接受了输入。
我不能理解的是，既然这是一个假想的机器，我们说它可以在多项式时间内解决 NP 问题有什么好处？我的意思是，我还可以理论化一个在 O(1) 中解决 NP 问题的神奇机器，如果它可能永远不存在，我能从中获得什么？
提前致谢。
非确定性图灵机是一个难以掌握的概念。尝试其他一些观点：
与其运行一个可能是最幸运的猜测者的神奇图灵机，不如运行一个更神奇的元机器，在平行宇宙中设置无限数量的随机猜测独立图灵机。每个可能的猜测序列都是在某个宇宙中进行的。如果在至少一个宇宙中机器停止并接受输入，这就足够了：问题实例被建立这些平行宇宙的元机器接受。如果在所有宇宙中机器拒绝或未能停止，则元机器拒绝实例。
与其进行任何类型的猜测或分支，不如考虑一个人试图说服另一个人该实例应该被接受。第一个人提供一组非确定性图灵机要做出的选择，第二个人检查机器是否接受带有这些选择的输入。如果是这样，第二个人就被说服了；如果没有，第一个人就失败了（这可能是因为实例无法通过任何选择序列被接受，或者因为第一个人选择了糟糕的选择序列）。
忘记图灵机。如果问题可以用存在二阶逻辑中的公式来描述，则该问题属于 NP 。也就是说，您采用普通的命题逻辑，允许对命题变量使用任何量词，并在开始时允许在集合、关系和函数上添加存在量词。例如，图的三着色性可以用一个公式来描述，该公式从对颜色（节点集）的存在量化开始：
∃R∃G∃B
每个节点都必须着色：
∃ R ∃ G ∃ B (∀ x (R(x) ∨ G(x) ∨ B(x)))
并且没有两个相邻节点可能具有相同的颜色——称为边关系 E：
∃ R ∃ G ∃ B (∀ x (R(x) ∨ G(x) ∨ B(x))) ∧ (∀ x,y ¬ (E(x,y) ∧ ((R(x) ∧ R( y)) ∨ (G(x) ∧ G(y)) ∨ (B(x) ∧ B(y)))))
对二阶变量的存在量化就像一个非确定性的图灵机做出完美的猜测。如果你想说服某人公式 ∃ X (...) 为真，你可以从给出 X 的值开始。多项式时间 NTM 和这些公式不仅“相似”而且实际上等价于 Fagin 定理，它开始了描述性复杂性领域：复杂性类的特征不是图灵机而是逻辑公式类。
你还说
我还可以理论化解决 O(1) 中的 NP 问题的神奇机器
是的你可以。这些被称为预言机（与 DBMS 无关），它们在复杂性理论中产生了有趣的结果。例如，Baker-Gill-Solovay 定理指出存在预言机 A 和 B，使得对于可以访问 A 的图灵机，P=NP，但对于可以访问 B 的图灵机，P≠NP。（A 是一个非常强大的预言机，它使非确定性无关紧要；B 的定义有点复杂，并且涉及对角化技巧。）这是一种元结果：任何解决 P 与 NP 问题的证明都必须是敏感的足以定义图灵机，当您添加某种预言机时它会失败。
非确定性图灵机的价值在于它们提供了复杂性类 NP（和其他）的相对简单的计算表征：您可以考虑一个几乎普通的计算机，而不是计算树或二阶逻辑公式被（相对地）略微修改，以便它可以做出完美的猜测。
您从中获得的是，您可以通过证明 NTM 可以在多项式时间内解决问题来证明问题存在于 NP 中。
换句话说，您可以使用 NTM 来找出给定问题是否属于 NP。
根据定义，NP 代表非确定性多项式时间，可以在Wikipedia中查找。
随机选择和检查（或组装）下一个潜在解决方案的非确定性图灵机的化身将以一定的概率在多项式时间内解决一个 NP 问题（如果它是“最幸运的可能”，它将绝对确定地在多项式时间内解决该问题猜测者”）。
因此，说 NTM可以在多项式时间内有效地解决问题意味着该问题在 NP 中。这又等价于 NP 类问题的定义。
我认为你的答案在你的问题中。换句话说，给定一个问题，如果你能找到解决它的 NTM，你就可以证明它是一个 NP 问题。
NP问题是一类特殊的问题，NTM只是检查给定问题是否属于该类的工具。
请注意，NTM 不是特定的机器——它是一整类机器，它们具有明确定义的规则，它们可以做什么和不可以做什么。为了使用“神奇”机器，您需要定义它们，并显示它们对应的问题的复杂性类别。
有关更多信息，请参阅http://en.wikipedia.org/wiki/Computational_complexity_theory#Complexity_classes 。
来自希伯来语维基百科 - “NTM 主要是一种思考工具，实际上不可能实现这样的机器”。您可以将术语“NTM”替换为“在每一步尝试所有可能步骤的算法”或“在每一步都选择最佳下一步的算法”。我想你理解其余的。NTM 在这里只是为了帮助我们可视化这样的算法。您可以在这里看到它应该如何帮助您进行可视化（在 Pascal Cuoq 的回答中）。
我们得到的是，如果我们有神通猜测正确的步骤，这将永远是正确的，我们可以解决 POLYTIME 中的 NPC 问题。当然，我们不能总是“猜”出正确的步骤。所以是想象的。但正如虚数适用于现实世界的问题一样，结果在理论上也很有用。
以这种方式变形原始问题的一个积极方面是我们可以从不同的角度解决它们。在理论领域，这是一件好事，因为我们有（1）我们可以采用更多的方法（因此更多的论文）和（2）如果它们可以在其他领域中使用，我们可以使用更多的工具。