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?
Algorithms – What Does It Mean for an Algorithm to Be Sound and Complete
algorithmsterminology
Related Topic
- Algorithms – Understanding Polynomially Bigger/Smaller Functions
- Algorithm Performance – Expected Running Time vs. Average Running Time
- How does Jump Point Search algorithm work and why is it so efficient
- BigO Algorithms – What Does ‘Upper Bound’ Mean?
- Algorithms – What Does Pi Mean in This BFS Algorithm Pseudocode?
- Project Architecture – Understanding the Meaning of Architecture in Projects
Best Answer
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.