algorithm - 算法的健全性和完备性

Question

我对算法的健全性和完整性感到困惑。

可靠的算法永远不会返回错误的结果。算法有没有可能不返回任何东西？

一个完整的算法将处理所有输入。算法返回的结果是否影响算法的完备性？

例如:如果一个排序算法将接受所有输入并返回一个列表，但它不保证返回一个排序列表，它只是一个不健全的算法，但是，它是否完整？

Answer 1

设 S 为所有正确答案的集合。

sound 算法永远不会在 S 中包含错误答案，但它可能会错过一些正确答案。 => 不一定“完整”。

一个完整算法应该得到S中的每一个正确答案:包括完整的正确答案集。但它可能包含一些错误的答案。它可能会为单个输入返回错误的答案。 => 不一定是“声音”。

所以，

A sound algorithm will never return a false result. Is it possible that the algorithm doesn't return anything?

一定是对的。但它什么也不能返回。(遗漏部分)

For example, if a sorting algorithm will take all inputs and return a list, but it doesn't guarantee to return a sorted list, it simply a unsound algorithm, however, is it complete?

好吧，这取决于。

如果算法返回的列表构成集合 S，则它是完整的，因为每个正确答案都包含在内。这并不一定意味着每个输出都是正确的。例如。 S = {b1, b2}。假设对于输入a1，正确的输出是b1；对于输入a2，正确的输出是b2。如果算法为 a1 返回 b2，为 a2 返回 b1，它是完整的但不健全。

另一方面，如果算法总是为a1 和a2 返回解决方案b1，则显然不完整。

因此，您不能仅仅根据算法的可靠性来推断算法是否完备，反之亦然。

引用7 Ways to Approach Soundness and Completeness , 还有 here .