Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question
    
I suggest you reevaluate what answer you accepted given that one is wrong. – BlackJack Mar 20 '12 at 19:44
    
Just did that :) – mutelogan Mar 20 '12 at 20:13
up vote 35 down vote accepted

These are very specific terms as related to logic.

Here are some starting points:

http://en.wikipedia.org/wiki/Soundness

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.

share|improve this answer
    
Thanks. I was really confused about what soundness means. I was getting multiple answers. – mutelogan Mar 20 '12 at 20:10
    
Happy if it helped... :) – Erik Dietrich Mar 20 '12 at 20:11
11  
An example would be the Binary Search, It's sound, but it's not complete. It can't work on non-sorted lists. – Malfist Mar 20 '12 at 20:36
1  
@Malfist but isn't the 'world of the program' sorted lists? – Andres Oct 27 '13 at 23:02
    
@Malfist Why it cannot? I can easily supply an unsorted list. The fact that I will get the wrong results means that it is unsound rather than incomplete. So that definitions are interchangable, as they are in CS. Isn't it? – Valentin Tihomirov Jan 31 at 22:20

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.

share|improve this answer
    
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. – itsbruce Nov 28 '14 at 18:31
1  
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 Jun 8 '15 at 1:45

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

enter image description here

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.