Is the following example correct about whether an inference algorithm is sound and complete?

Suppose we have needles a, b, c in a haystack, and have also an inference algorithm that is designed to find needles.

  • sound - Only needles a, b and c are obtained.

  • complete - Needles a, b and c are obtained. Other hay may also be obtained.


You have almost got it right, but your definition of soundness is not quite right, or perhaps too subtle.

I would say that the inference algorithm is sound if everything returned is a needle (hence some needles may be missed) and complete if all needles are returned (hence some hay may be returned too).

| cite | improve this answer | |
  • $\begingroup$ This may be an issue of language semantics. Assuming the only objects beside hay are the three needles, the OP's phrasing is correct. $\endgroup$ – Raphael May 9 '12 at 13:22
  • 1
    $\begingroup$ In any case, my answer spells it out to make it clearer. $\endgroup$ – Dave Clarke May 9 '12 at 13:24
  • 1
    $\begingroup$ Indeed, if the phrasing were "Only needles a, b and c can be obtained" I wouldn't have given an answer. $\endgroup$ – Dave Clarke May 9 '12 at 14:03
  • $\begingroup$ So it seems sound means that the algorithmic function has range being needles, and it being complete means the function is surjective to the set of needless in the haystack ;-) $\endgroup$ – Musa Al-hassy Dec 6 '18 at 15:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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