用非决定论来检测小集团？

Question

我试着用集团问题来理解非决定论。

在计算机科学中，团问题是指图中与寻找特定完备子图(“团”)有关的任何问题，即每一对元素连通的元素集。

假设我有一个有节点A，B，C，D，E，F的图，我想决定一个4的团是否存在。

我对非决定论的理解是通过取四个节点(B，C，D，F)来猜测，并检查所有4个节点之间是否存在连接。如果它存在，我得出结论，一个集团存在，如果不存在，我得出一个集团不存在的结论。

然而，我不知道这如何帮助解决问题，因为我可能做出了错误的选择。

我想我正试着理解非决定论在一般情况下的应用。

Answer 1

非确定性选择不同于随机或任意选择。当使用非确定性时，如果任何可能的选择都会导致算法输出是，那么这些选择中的一个将被选择。如果没有这样的选择，那么就会做出任意的选择。

如果这看起来像是作弊，从某种意义上说是这样。如何使用确定性计算机、随机算法或具有大量处理器但只能在每个核上完成少量工作的并行计算机有效地实现非确定性是未知的。这些问题分别是P= NP、BPP = NP和NC = NP问题。因此，不确定性主要是解决问题的一种理论方法。

希望这能有所帮助！