I heard different interpretations of sound and complete. I understand that completeness means finding a solution if there is one. What does it mean to say an algorithm is sound.
What does it mean to say an algorithm is Sound and Complete?
These are very specific terms as related to logic.
Here are some starting points:
Basically, soundness (of an algorithm) means that the algorithm doesn't yield any results that are untrue. If, for instance, I have a sorting algorithm that sometimes does not return a sorted list, the algorithm is not sound.
Completeness, on the other hand, means that the algorithm addresses all possible inputs and doesn't miss any. So, if my sorting algorithm never returned an unsorted list, but simply refused to work on lists that contained the number 7, it would not be complete.
It is complete and sound if it works on all inputs (semantically valid in the world of the program) and always gets the answer right.
I find Erik Dietrich's answer a tad confusing. The following is better:
An algorithm is sound if, anytime it returns an answer, that answer is true. An algorithm is complete if it guarantees to return a correct answer for any arbitrary input (or, if no answer exists, it guarantees to return failure).
Two important points:
Consider for an example a sorting algorithm A that receives as input a list of numbers. We say that A is sound if every time it returns a result that result is a sorted list. Likewise, we say that A is complete if guarantees to return a sorted list any time we give it a list of numbers.
These terms came from computation theory, so they are more meaningful in the context of computation theory than in the context of software engineering
In most standard models of computation, computing problems are represented as languages. A language is a set of strings. An algorithm, then, is just a system or procedure that decides whether a given string is a member of some language (by returning true or false). In software engineering terms, computation theory is specifically concerned with functions that look like this, assuming strings are immutable:
We call this function complete if it returns true for every argument which is a member of the language. We call it sound if it returns false for every argument which is not a member of the language.
In other words, it's complete if it always returns true when we want it to return true, and sound if it always returns false when we want it to return false.
How does this translate to other kinds of function? As it turns out, it's almost always possible to stuff an arbitrary amount of data into a string and reconstitute it inside the function. So the restriction on argument type and arity is nothing more than a theoretical simplification. The restriction on return type is more important, however. Problems which call for a boolean result are called decision problems. Much computation theory involves decision problems; the sets P and NP are restricted to decision problems (and NP, at least, couldn't be reasonably defined without this restriction). The halting problem is another example of a heavily-studied decision problem.
It's my opinion that these terms don't generalize outside the domain of decision problems, so the difference between them is not really meaningful when discussing a general function.
There are much better answers at the SO. Basically, you provide some data collection and criteria to search. Sound algorithm catches you only the fish that matches the criteria but it may miss some data items. Complete algorithm produces a superset of requested results, which means that you receive some garbage on top of requested results. Sound algorithm is more conservative.
Statistician would probably say that sound algorithm is biased towrads type I errors (it does not accept the correct candidates), whereas complete algorithm is biased towards type II errors (to accept the false candidates).
Thank you for your interest in this question.
Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).
Would you like to answer one of these unanswered questions instead?