[암호학] 13. Classes 1

Classes

Complexity Theory에서 Classes란 Problem들의 집합을 의미한다.

우리는 앞에서 Problem이 무엇인지 알고 왔기 때문에 Classes도 큰 어려움없이 이해할 수 있다.

Problem의 크기가 $|2^{|\Sigma^*|}|$였으므로 Classes의 크기는 $|2^{|2^{|\Sigma^*|}|}|$가 되고 이는 어마어마하게 많다는 것을 의미한다.

그리고 앞서 말했듯이 쉬운 문제 -> 빨리 풀린다, 어러운 문제 -> 푸는데 오래 걸린다, 굉장히 어려운 문제 -> 푸는데 언제 끝날지 모른다. 를 의미한다.

 

그럼 이제 Classes에는 어떤 것들이 있는지 알아보자.

 

Classes D

Classes D는 Decidable한 문제로 입력 $x$가 Language $L$에 포함되면 즉, $x \in L$이면 Yes, 아니면 No를 도출한다.

여기에서 $L$은 뭔지 모르지만 일단 어떤 Problem $L$ ($L \in D$)이 있다고 하고 그런 Problem을 해결하는 $M$이 있다고 하자.

$M(x) = $ Yes $(x \in L)$

$M(x) = $ No $(x \notin L)$

Classes D 의 특징은 시간이 충분히 길면 문제가 해결됨이 보장된다.

 

Classes E, co-E

Classes E는 Enumerable한 문제로 입력 $x$가 Language $L$에 포함되면 즉, $x \in L$이면 Halt, 아니면 무한루프에 빠진다.

앞으로 편의상 무한루프인 상태를 $\infty$ 라고 표현한다.

역시 어떤 Problem $L$ ($L \in E$)을 해결하는 $M$이 있다고 하자.

$M(x) = $ Halt $(x \in L)$

$M(x) = \infty (x \notin L)$

여기서 Halt는 해당 문자열을 출력하는게 아니라 프로그램이 정지한다는 뜻이다.

 

Classes co-E는 E의 반대라고 생각하면 된다.

$M(x) = \infty (x \in L)$

$M(x) = $ Halt $(x \notin L)$

즉, $L \in E \rightarrow L^c \in co$-$E$이다.

 

Classes D, E, co-E

우선 둘이 생긴게 굉장히 닮았다.

Classes D에서 Yes -> Halt, No -> $\infty$로 바꾸면 Classes E가 된다.

실제로 이는 참이고 이게 성립하기 때문에 $D \subset E$가 성립한다.

 

하지만 역은 성립하지 않는다.

E가 끝나지 않았다면 Halt인지 $\infty$인지 알 수 없기 때문이다.

이는 Halting Problem이 해결되지 않는 이유이기도 하다.

 

같은 이유로 Classes D에서 Yes -> $\infty$, No -> Halt로 바꾸면 Classes co-E가 된다.

즉 $D \subset co$-$E$도 성립한다.

 

그렇다면 일단 집합을 그리면 아래와 같이 나온다. (나중에 모양이 바뀔 것이다.)

Classes