# What does it mean to say an algorithm is Sound and Complete?

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?

• I suggest you reevaluate what answer you accepted given that one is wrong. Commented Mar 20, 2012 at 19:44
• Just did that :) Commented Mar 20, 2012 at 20:13

These are very specific terms as related to logic.

Here are some starting points:

http://en.wikipedia.org/wiki/Completeness_(logic)

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.

• Thanks. I was really confused about what soundness means. I was getting multiple answers. Commented Mar 20, 2012 at 20:10
• Happy if it helped... :) Commented Mar 20, 2012 at 20:11
• An example would be the Binary Search, It's sound, but it's not complete. It can't work on non-sorted lists. Commented Mar 20, 2012 at 20:36
• @Malfist but isn't the 'world of the program' sorted lists? Commented Oct 27, 2013 at 23:02
• “An algorithm misbehaves on invalid inputs” does not affect soundness or completeness, so neither binary search nor comparison sorts are relevant — both algorithms are sound and complete for valid inputs. Commented Dec 15, 2017 at 0:00

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:

1. Soundness is a weak guarantee. It does not promise that A will terminate.
2. Soundness and Completeness are related concepts; infact they are the logical converse of each other. i.e. Soundness says that if an answer is returned that answer is true. Completeness says that an answer is true if it is returned.

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.

• Why are you confused? "An algorithm is sound if, anytime it returns an answer, that answer is true." means the same as "Basically, soundness (of an algorithm) means that the algorithm doesn't yield any results that are untrue." These mean the same thing. As for your (very brief) definition of Completeness, it matches nothing in the wikipedia link and you cite no reference of your own. I have to say, Erik's definitions are more practically useful. If yours are correct, you have to provide better evidence and more meat. Commented Nov 28, 2014 at 18:31
• Just to clarify, when you say "Completeness says that an answer is true if it is returned", you mean that the answer is "correct" right?
– Dois
Commented Jun 8, 2015 at 1:45
• “An answer is true if it is returned” means literally the same as “if an answer is returned it is true”. Also, answers can’t be “true”, only correct. softwareengineering.stackexchange.com/a/311649/21277 is more correct. Commented Dec 14, 2017 at 23:58

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:

``````boolean some_function(string argument){...}
``````

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).