theory - 非确定性图灵机如何工作？

Question

我知道它们不是真实的，只要有两个选项，它们似乎就会分支计算，而不是选择一个。但是，例如，如果我这样说:

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

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

Answer 1

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