[컴퓨터 공학, 알고리즘] completeness vs soundness

completeness: 모든 정답 사례를 찾아낼 수 있다.

soundness: 어떠한 오답 사례도 정답 사례라고 잘못 판단하지 않는다. 

 

true/false positive/negative 개념을 동원하면 이해하기가 비교적 쉽다.

true positive = 참이라고 예측했고 실제로도 참인 경우

false positive = 참이라고 예측했으나 실제로는 거짓인 경우

false negative = 거짓이라고 예측했으나 실제로는 참인 경우

true negative = 거짓이라고 예측했고 실제로도 거짓인 경우

 

예를 들어 보자.

A B C D E F 라는 사람이 있고, A B C 는 거짓말 쟁이고, D E F는 보통 사람이라고 하자.

그리고 우리는 보통 사람을 찾아내는 알고리즘을 구현해야 한다.

 

우리가 만든 알고리즘이 completeness를 만족한다면 그 알고리즘은 반드시 D E F 에 대해서 보통 사람이라고 이야기한다. 하지만 이것이  A B C가 거짓말 쟁이임을 말하지는 않는다. 즉, completeness를 만족하지만 soundness를 만족하지 않았다면 A B C 중 최소 한 명 이상을 평범한 사람이라고 잘못 지적한 것이다. (false positive)

 

우리가 만든 알고리즘이 soundness를 만족한다면 그 알고리즘은 A B C를 평범한 사람이라고 잘못 지적하지는 않는다. 만약 soundness는 만족하지만 completeness를 만족하지 않는다면, A B C 에 대해서는 거짓말 쟁이임을 잘 찾아내지만, D E F 중에서 최소 한 명을 거짓말 쟁이라고 잘못 판단하게 될 것이다. (false negative)

 

따라서, completeness와 soundness를 전부 만족한다면, 어떠한 false 결정도 하지 않게 된다.

 

completeness 만족 & soundness 만족 => D E F 보통 사람 / A B C 거짓말 쟁이 (완벽하게 모든 사례 정답!)

completeness 만족 & soundness 불만족 => A D E F 보통 사람 / B C 거짓말 쟁이 (이 경우 A가 false positive)

completeness 불만족 & soundness 만족 => E F 보통 사람 / A B C D 거짓말 쟁이 (이 경우 D가 false negative)