algorithm - 非确定性算法

Question

我需要对非确定性算法的简单描述。我们可以将非确定性算法与具有并行处理器的计算机进行比较吗？请有人准确地向我解释一下非确定性算法

Answer 1

非确定性算法是在非确定性图灵机上运行的算法。
该算法中的每个计算都可以分支为 2 个同时计算的计算。

无确定性算法示例：
Set Cover：“猜测”顶点的子集，并检查它是否是有效的覆盖。
猜测是：对于每个元素：检查一种可能性，它是在集合中，而不是在集合中。

它不是并行处理器，因为在这里（非确定性算法），分支的数量不受限制，而在并行处理器中是。在并行计算中，您仍然需要执行2^nOP 来查找顶点覆盖，而在非确定性算法中，您只执行n具有n不同分支的操作​​。

非确定性机器更像是量子计算机，而不是并行处理。[请注意，当然，假设 P!=NP，量子计算机仍然比非确定性图灵机“更弱”]。