Soundness and completeness are important concepts that regularly tangle people up for some reason. So, here's several different ways to think about them. Choose the one that makes sense to you!
Purely Logical
An algorithm A gives a yes or no response to input question q (drawn from the set of all inputs Q). So, A(q) is equal to yes or no.
A is sound exactly when: A(q) = yes guarantees that the true answer to input question q is yes. (That is, A(q) = yes implies the true answer to q is yes.)
A is complete exactly when: A is guaranteed to give a yes response any time the true answer to input question q is yes. (That is, the true answer to q is yes implies A(q) = yes.)
(Note that these are converses of each other.)
Drawing Boundaries on the Set [or "Why the Word Complete?"]
Think of an algorithm that gives yes or no answers as trying to draw a circle around all the members of the set of right answers. A complete algorithm should get every right answer in that circle: include the complete set of right answers. However, it might include a few wrong answers in the quest to include every last right answer.
(In contrast, a sound algorithm never includes a wrong answer in its circle, but it might miss a few right answers.)
Engineering [or "Why the Word Sound?"]
Constructing a building on a "sound foundation" means building it on something that will hold it up.
If I'm the contractor building your foundation and you ask me "is it strong enough for the building to stand?", you want me to be a "sound decider".
If I say "yes", you want that to be a GUARANTEE that the building will stand.
If I have doubts, I should say "no" (even if I'm not sure the building will fall).
In that sense, engineering fudge factors are like "erring on the side of soundness" to guarantee success.
Disease Testing
Say I'm a blood bank. I give you a test to see if a donor is positive for HIV. If they are positive, I need to reject the donation (or keep it in an HIV positive pool depending on issues outside the scope of this example). If they are negative, I can take the donation.
Now, do I want a sound test or a complete test? Unlike the engineering example above, I want my guarantees on the "no" answer. When my test says "No", I want it to be a guarantee of HIV-negative status. That's completeness.
Tour de France Drug Test
You're a cyclist who wants to ride the Tour de France. You're being tested for doping. The test says either "yes, you doped" or "no, you didn't". Do you want the test to be sound or complete?
Say the test comes back "yes". That's bad for you, right?
If you're not doping, you want a guarantee that it will not come back yes. Soundness gives that guarantee. (It guarantees that a yes means true doping; so, if there's no true doping, there can be no "yes" response.)
If you are doping, you'd rather not have completeness. Completeness guarantees that every case of true doping will be detected!
False Positives, False Negatives
A "false positive" response is a "yes" when the true answer is no. A "false negative" response is a "no" when the true answer is yes.
Soundness guarantees no false positives.
Completeness guarantees no false negatives.
Type I and Type II Errors
This doesn't help unless you know what the things are, and why would you remember which one is "the first type" and which is "the second type". But, what the heck..
Soundness means no Type I errors.
Completeness means no Type II errors.
The Dirty Secret
Remember that blood testing example? Say the blood bank built a little machine that does the test and spits out an answer "yes, accept donation" or "no, reject donation". In other words, their machine does the blood test and then reverses the result.
All of the sudden, the blood bank wants soundness rather than completeness.
What happened? Soundness and completeness are duals of each other. Invert the sense of the problem, and you swap the two terms' meanings.
Another Place To Look
Didn't help? Try this post on soundness and completeness.
Cheers,
Steve
Here is how I remember the difference between the two:
ReplyDeleteOne night at my place, we were cooking hashbrowns in the kitchen, when, all of a sudden, every single smoke alarm in our unit went off. We turned the stove off, aired all of the smoke out of the room (of which there wasn't really any). Still the smoke alarms were beeping their awful beeping noise!
We called the emergency line; they said they would call back; then we just got smart and flipped the breaker switch. Fire alarms off. (Then I got really paranoid about them actually being carbon monoxide alarms, but that's another story.)
Given that it was just after we went over soundness and completeness in CS311, I figured maybe it wasn't such a bad thing it went off when there was hardly any smoke. Because you would rather have the soundness of the alarms tell you if there is any possibility of a fire (pun intended) than them not going off and, well, suffocating and dying, of course.