Soundness and Completeness of a algorithm
algorithm
Solution
Let S be the set of all right answers.
A sound algorithm never includes a wrong answer in `S`, but it might miss a few right answers. => not necessarily "complete".
A complete algorithm should get every right answer in `S`: include the complete set of right answers. But it might include a few wrong answers. It might return a wrong answer for a single input. => not necessarily "sound".
So,
A sound algorithm will never return a false result. Is it possible that the algorithm doesn't return anything?
It must be right. But it can return nothing.(missed part)
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?
Well, it depends.
If the returned lists from the algorithm forms the set `S`, it's complete because every correct answer is included. It doesn't necessarily mean that every single output is correct. E.g. `S = {b1, b2}`. Assume that, for input `a1`, the correct output is `b1`; For input `a2`, the correct output is `b2`. If the algorithm returns `b2` for `a1`, `b1` for `a2`, it's complete but not sound.
On the other hand, if the algorithm always returns the solution `b1` for both `a1` and `a2`, it's obviously not complete.
So you can't just infer whether an algorithm is complete or not by its soundness, and vice versa.
Refer to 7 Ways to Approach Soundness and Completeness, also here.
Problem
I am confused with soundness and completeness of algorithms. A sound algorithm will never return a false result. Is it possible that the algorithm doesn't return anything? A complete algorithm will address all inputs. Does the results the algorithm returns affect the completeness of the algorithm? For example: if a sorting algorithm will take all inputs and returns a list, but it doesn't guarantee to return a sorted list, it is simply an unsound algorithm, however, is it complete?