[암호학] 2. Halting Problem

Complexity Theory 세계로...

Complexity Theory(계산복잡도 이론)은 암호학에 필요한 이론이라고 한다.

우리가 알고리즘때 사용하는 Big-O표기법도 Complexity Theory에서 나왔다. (알고리즘도 여기에 포함된다고 한다.)

즉 Complexity Theory란 튜링머신(컴퓨터)이 어떤 연산을 하는데 얼마나 걸리는지를 분석하는 컴퓨터 과학 분야이다.

 

미리 알아둬야할 컨셉이 있다.

• 어떤 문제가 어렵다는 것은 해당 문제를 해결하는 시간이 오래 걸린다는 뜻이다.

사실 "오래 걸린다"도 추상적이긴 하지만 "어렵다"도 마찬가지이니 의미만 이해하고 넘어가자.

 

Halting Problem

어떤 프로그램과 인풋이 주어졌을 때 해당 프로그램이 정지하는 지(끝나는 지) 판정하시오.

Halting Problem(정지 문제)는 Complexity Theory에서 유명한 문제라고 한다.

문제의 이해는 굉장히 쉬울 것이다.

하지만 이 문제를 풀 수 있는 방법은 없다.

 

만약 그 프로그램의 시간이 얼마나 걸리든 결과가 나온것을 확인했다면 YES가 된다.

하지만 프로그램 결과가 1분, 1시간, 1일, 1년 ... 수많은 시간이 지나서 결과가 나오지 않았다고 해도 NO라고 답할수는 없다.

그것보다 더 긴 시간을 필요로 하는 프로그램일 수 있기 때문이다.

 

이는 해결할 수 없음이 증명돼있다.

 

이 문제도 암호학을 이해하는데 사용되는 개념중 하나라고 한다.