Soundness and Completeness of a algorithm

Question

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?

Answer 1

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.

Answer 2

This analogy will make you understand the concept.

There is a fishing contest. The goal is to catch fishes heavier than 1 Kg. There are two contenders, Sunada and Compila. Each one uses their own lake to catch fishes. Each lake have exactly same number of fishes(100 fishes) and among those fishes, they have exactly same number of fishes weighting more than 1 Kg (50 fishes).

The referee starts the competition with a whistle. They both catch numerous fishes until the end of the time. Now it comes to count fishes which comply to the rule. The referee starts to weight all fishes caught by Sunada first. Surprisingly, all fishes caught by Sunada weight more than 1 Kg! But he caught only 45 fishes.

On the other hand, Compila caught 60 fishes. It seems Compila wins but referee didn’t decide yet. Because there may be less than 45 fishes weighting more than 1 Kg. After counting and weighting, referee says there are 50 fishes complying the rule which makes Compila the winner.

Now in this analogy, all fishes caught by Sunada comply the rule, which makes him perfectly sound! Compila, on the other hand caught all fishes that comply the rule and that makes Compila the perfectly complete!