In the context of interactive proof systems, we often see the term "sound" used. What is the sense of this word?

  • 4
    $\begingroup$ Context and/or reference, please. $\endgroup$
    – hunter
    Nov 4 '14 at 10:34
  • $\begingroup$ This definition is likely from interactive proof systems. Complete means verifying party would accept for a valid common input, sound means will reject for an invalid input. Unlike logic, both with some probability, resulting in "soundness error" being the probability of accepting a wrong answer. In the context of a proof of equality of two logarithms, "wrong" would mean no NP-witness exists, so response must being calculated with "arbitrary" algorithm. $\endgroup$ Jan 8 '15 at 22:04

Look up the words sound/complete from logic. Complete roughly means that a method can solve every instance. Sound roughly means that the answer it gives is correct.

For example, assume that we have a program that's supposed to tell when an element belongs to a set. A sound program will only answer "yes" when the element actually belongs to the set. An unsound program might sometimes answer "yes" even though the element doesn't belong to the set. For some instances unsoundness might be OK, if it happens very rarely. An example is a primality tester, which might falsely claim with a very small probability that a composite number is prime.

This applies similarly to any decision procedure for example a program that has to declare whether $X$ is secure in some model $Y$.

  • $\begingroup$ Ok, thank yout for your answer. $\endgroup$
    – Dingo13
    Nov 5 '14 at 11:46

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