복잡도 이론

컴퓨터 문제는 다양한 종류가 있는데, 쉬운 문제도 있고 어려운 문제도 있다. 예를 들어 정렬 문제는 쉬운 문제다. 일련의 수를 오름차순으로 정렬해야 한다고 가정해 보자. 작은 컴퓨터로도 백만 개의 숫자를 빠르게 정렬할 수 있다. 이를 강의 일정을 세우는 문제와 비교해 보자. 같은 시간에 같은 강의실에서 두 개의 수업이 열리지 않는다는 등의 합리적인 제약 조건을 만족하는 대학 전체의 수업 일정을 짜야 한다고 가정해 보자. 강의 일정 문제는 정렬 문제보다 훨씬 더 어려운 것 같아 보인다. ¹ 수업이 천 개만 있어도 최적의 시간표를 찾는 데는 슈퍼컴퓨터를 사용해도 몇 세기가 걸릴 수 있다.

문제에 따라 계산하기 쉽고 어려운 이유는 무엇인가?

이것이 복잡도 이론의 핵심 질문이다. 놀랍게도 이 질문은 40년 넘게 집중적으로 연구되어 왔지만 아직 그 해답을 알지 못한다. 지금부터 이 매혹적인 질문과 그 파급 효과에 대해 알아보자.

지금까지 복잡도 이론의 중요한 성과 중 하나로, 연구자들은 계산 난이도에 따라 문제를 분류하는 우아한 체계를 발견했다. 이는 화학적 성질에 따라 원소를 분류하는 주기율표와 유사하다. 이 체계를 사용하면 특정 문제가 계산적으로 어렵다는 것을 증명할 수 없더라도 그 증거를 제시하는 방법을 증명할 수 있다.

계산적으로 어려워 보이는 문제에 직면했을 때 몇 가지 선택지가 있다. 첫째, 문제의 어떤 측면이 어려움의 근원이 되는지 이해함으로써 문제를 더 쉽게 해결할 수 있도록 바꿀 수 있다. 둘째, 문제에 대한 완벽한 해결책보다는 덜 완벽한 해결책에 만족할 수 있다. 어떤 경우에는 완벽한 해결책에 근접한 해결책을 찾는 것이 비교적 쉽다. 셋째, 어떤 문제는 최악의 상황에서만 어렵지만 대부분의 경우 쉽게 해결할 수 있다. 경우에 따라서는 느리지만 일반적으로 빠르게 실행되는 절차에 만족할 수도 있다. 마지막으로, 특정 작업의 속도를 높일 수 있는 무작위 계산과 같은 다른 유형의 계산을 고려할 수 있다.

복잡도 이론의 직접적인 영향을 받은 응용 분야 중 하나는 고대의 암호화 분야다. 대부분의 분야에서는 쉬운 계산 문제가 어려운 문제보다 선호되는데, 이는 쉬운 문제를 푸는 데 드는 비용이 더 저렴하기 때문이다. 암호학은 쉬운 계산 문제가 아니라 어려운 계산 문제가 필요하다는 점에서 특별하다. 암호문은 키나 비밀번호 없이는 해독하기 어려워야 한다. 복잡도 이론은 암호학자들이 혁신적인 새로운 암호를 설계할 수 있도록 계산하기 어려운 문제의 방향을 제시했다.

계산 가능성 이론

20세기 전반기에 쿠르트 괴델, 앨런 튜링, 알론조 처치와 같은 수학자들은 컴퓨터로 풀 수 없는 기본적인 문제가 있다는 사실을 발견했다. 이러한 현상의 한 가지 예로 수학적 명제가 참인지 거짓인지 판단하는 문제를 들 수 있다. 이 문제는 수학자들의 생계와도 같은 문제다. 수학의 영역에 속하는 문제이기 때문에 컴퓨터로 해결할 수 있는 것이 당연해 보이지만, 어떤 컴퓨터 알고리즘도 이 작업을 수행할 수는 없다.

이 심오한 결과의 결과 중에는 컴퓨터의 이론적 모형에 관한 아이디어가 개발되어 결국 실제 컴퓨터의 제작으로 이어지는 데 도움이 되었다.

계산 가능성과 복잡도 이론은 밀접한 관련이 있다. 복잡도 이론에서는 문제를 쉬운 문제와 어려운 문제로 분류하는 것이 목표인 반면, 계산 가능성 이론에서는 문제를 해결할 수 있는 문제와 그렇지 않은 문제로 분류한다. 계산 가능성 이론에서의 개념이 복잡도 이론에서 종종 사용된다.

오토마타 이론

오토마타 이론은 계산에 대한 수학적인 모형의 정의와 속성을 다룬다. 이러한 모형은 컴퓨터 과학의 여러 응용 분야에서 중요한 역할을 한다. 유한 오토마타라고 하는 한 모형은 텍스트 처리, 컴파일러 및 하드웨어 설계에 사용된다. 문맥 없는 문법이라고 하는 또 다른 모형은 프로그래밍 언어와 인공 지능에 사용된다.

오토마타 이론은 계산 이론를 공부하기 위한 좋은 시작점이다. 계산 가능성과 복잡도 이론은 컴퓨터에 대한 엄밀한 정의를 필요로 한다. 오토마타 이론은 컴퓨터 과학의 다른 비이론적 영역과 관련된 개념을 소개하므로 계산에 대한 공식적인 정의를 연습할 수 있다.

참고 문헌

1. M. Sipser, Introduction to the Theory of Computation, 3rd ed. Cengage Learning, 2012.