非确定性图灵机是如何工作的？

Question

我知道他们不是真实的，只要有两个选项，他们似乎就会转移计算，而不是选择一个。但是，举个例子，如果我这样说：

“非确定性地猜测从图G到图H的顶点的双射p”(这里的上下文是图同构)

这是什么意思？我理解这个双射，但它说的是“非确定性猜测”。如果是猜测，这怎么是一种算法方法呢？它如何保证它会工作呢？

Answer 1

有不同的方式来描绘一个。我发现一个有用的模型是oracle模型。你有没有看过另一边的漫画，黑板上的派生词作为中间步骤之一是“在这里奇迹发生了”？在此版本的NDTM中，当您需要选择某些内容时，oracle会在磁带的正确部分写入正确的版本。(本文摘自Garey和Johnson的“计算机与难题”，这是他们关于NP-complete问题的经典著作。)然而，你不能假设你得到了正确的答案，而且可能没有正确的答案。

因此，当您不确定地猜测双射时，只要存在一个双射，您就得到了符合您的目的的正确双射。

这不是一个很好的算法基础，因为在非确定性状态下，实现非确定性图灵机的复杂性基本上是指数级的，而非确定性猜测的算法等价物是尝试每一个可能的双射。

从理论上讲，我会把它翻译为“如果有一个双射……”。从算法的角度来看，找另一本书，或者同一本书的另一个章节，因为这种方法对于即使是中等大的图也是无用的。

Answer 2

他们没有，他们只是说明了一个观点。基本上，他们所做的就是猜测答案，并检查它是否正确(确定性地)。不过，重要的不是猜测答案部分，而是检查答案是否正确。这就像是说，给定一个任意的解决方案，它是正确的吗？例如，有一些问题需要指数时间来计算，其中一些答案可以在多项式时间内检查，但有些答案不能。所以非确定性TM所做的是将这两个问题分开，可以快速检查的问题和不能快速检查的问题。然后这就提出了一个更大的问题，如果一组问题的解决方案可以比另一组更快地验证，那么它们的解决方案是否也可以更快地生成？这个问题还没有得到回答。

Answer 3

我相信这是指“非确定性地选择一个解决方案”，然后测试这个解决方案是否正确。由于测试了所有可能的选择(猜测)，因此解决方案是有保证的。