Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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

2 Answers 2

up vote 17 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

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 sound and complete 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
9  
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
    
@Malfist but isn't the 'world of the program' sorted lists? –  Andres Oct 27 '13 at 23:02

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

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.