complexity-theory - 什么是非确定性程序？

Question

我有一个问题......什么是非确定性程序？我有这个练习

为以下语言提供一个非确定性过程： L = {: G=(V,E) 有一个独立集 I st |I| >= k 和顶点 V\I 形成一个哈密顿循环}

谢谢！

Answer 1

非确定性过程或函数是对于给定输入值不会总是产生相同输出的过程。

例如： DateTime.GetCurrent 将是不确定的。Random.Next() 将是不确定的。Math.Sin() 希望是确定性的。如果您输入相同的值 10 次，您将获得 10 次相同的结果。

Answer 2

非确定性函数可以依赖于“预言机”。在您的示例中，oracle 将生成集合I，并且该函数只需要检查它是否具有指定的属性，即I是否独立，|I| >= k并V\I形成汉密尔顿循环。