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

Question

我知道他们不是真实的,只要有2个选项,他们似乎会分支计算,而不是挑选一个.但是,例如,如果我这样说:

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

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

Answer 1

有不同的方式来描绘一个。我发现预言机模型很有用。您是否看过《远方》漫画，其中黑板上的推导将“奇迹发生了”作为中间步骤之一？在此版本的 NDTM 中，当您需要选择某些内容时，预言机会将正确的版本写入磁带的右侧部分。（摘自加里和约翰逊，《计算机与难处理性》，这是他们关于 NP 完全问题的经典著作。）不过，你不能假设你已经找到了正确的答案，而且可能并不存在正确的答案。

因此，当您非确定性地猜测双射时，只要双射存在，您就会得到符合您目的的正确双射。

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

从理论的角度来看，我将其翻译为“如果存在双射这样......”。从算法的角度来看，找到另一本书，或同一本书的另一章，因为这种方法即使对于中等大小的图也是无用的。