据我了解，非确定性算法只是一个抽象概念，在现实中并不存在。因为它不能在确定性（真实）计算机上以多项式时间求解。
定义：“非确定性算法”是一种算法，它指定用于处理相同输入的多个路径，而没有指定将选择哪个选项。
那么问题来了：有副作用的算法可以被认为是非确定性的吗？如果是，那么为什么在那种情况下它不能在真实的 PC 上执行？
这是一个算法的例子：
算法的输入是字符串——“Hello user”。
接下来，提示用户选择 4 个菜单项之一，
而不指定应选择哪个项。
输出是“你好用户，你选择了第 n 个菜单项”
困境：该算法完全符合非确定性算法的描述，同时在确定性计算机上以多项式时间求解。
1) 为处理相同的输入数据指定了多个路径。
2）不可能提前预测会选择哪一个。
3) 任何结果都是正确的，无论在运行时选择的路径如何。
4）算法的结果可能不同，尽管处理的是相同的输入数据。
术语上存在混淆：严格数学意义上的某个算法等同于某个图灵机，原则上，“副作用”这样的概念不适用于它，因为 垫。原则上，其模型并不规定它们的存在。所以这个问题基本上是不正确的。
另一方面，编程中有许多类似的术语（非正式定义）：
当然，情况并非如此，问题是任意的非确定性算法在通常的严格伪代码中更难以描述。
例如，给定一个集合 A 和一个数 N 任务：找到至少一个 a ∈ A 使得 N 可以被 a 整除。
确定性算法很明显，检查 N 是否可被 a1 整除，然后可被 a2 整除，以此类推。如果 a i除以 N，则返回 a i。
非确定性算法也可以这样做，但不需要指定检查 A 的元素的顺序，即 例如，根据任意因素，可以在 a1 之前检查 a125。在实践中，这可以描述为，例如，使用多线程或向量操作。
关键的区别不是由于动作的并行化而获得了速度增益，甚至不是每次运行的结果可能不同，而是一组特定的可执行动作及其顺序并不完全由算法和输入数据。
完全没有意义的说法……这是温暖与柔软的比较……是的，很多像猫这样的温暖物体都是柔软的，但是如果你用脚敲打电池，它就绝不是柔软的。所以在这里，一些算法在非确定性机器上的计算复杂度可能小于这些算法在确定性机器上的模拟，但这不是一般规则。
以上所有推论都可能包含错误，可能不是最终的真相......