Computational Complexity Theory
서구 계산 이론의 전통에서 계산의 복잡도라는 개념은 논리학과 Alan Turing 이 제시한 '계산 가능성' 의 연구 결과에 뿌리를 두고 있다
복잡도 이론 (Complexity Theory) 은 주어진 문제를 풀기위해 계산과정에 필요로 하는 자원을 다루는 계산이론 (Theory of Computation) 의 일부이다. 가장 흔한 자원은 시간 (문제를 풀기위해 얼마나 많은 단계를 거치게 되는가) 와 공간 (문제를 풀기위해 얼마나 많은 메모리를 필요로 하는가) 이다. 이외에도 문제를 병렬적으로 풀기위해 얼마나 많은 병렬 프로세서가 필요한가 와 같은 다른 자원들이 고려될 수 있다. Complexity theory 는 필요한 자원과는 무관하게 어떤 문제를 풀 수 있는지 없는지를 다루는 계산가능성 이론 (Computability Theory) 과는 다르다.
단 하나의 "문제" 는 관련 질문들의 전체 집합이며, 이때 질문은 유한 길이의 문자열이다. 예를들면 인수분해 (factorize) 문제에서, 이진법으로 쓰여진 정수가 주어지고, 그 수의 소인수를 전부 반환한다. 어떤 특별한 질문을 instance 라고 부른다. 예를들면 "15 의 인수들을 구해라" 하는 것은 인수분해 문제의 한 instance 이다.
시간 복잡도 (time complexity) 는 가장 효율적인 (보통 bit 로서 측정된다) 알고리즘을 사용해서 한 문제의 instance 를 푸는데 걸리는 단계의 수를 의미한다. 즉 n bit 길이의 instance 가 n2 단계 내에 풀릴 수 있다면 그 문제는 n2 의 시간 복잡도를 가진다고 말한다. 물론 단계의 정확한 수는 사용되는 기계나 언어에 의존할 것이다. 그런 문제를 피하기 위해 보통 Big O notation 을 사용한다. 만일 어떤 문제가 일반적인 컴퓨터에서 시간 복잡도 O(n2) 를 가진다면, 대부분의 다른 컴퓨터에서도 복잡도 O(n2) 를 가질 것이므로, 이러한 notation 은 특별한 컴퓨터에 구애받지 않고 일반화 할 수 있게 해준다.
예) 잡초 깎기는 두배의 면적을 깎는데는 두배의 시간이 걸리기 때문에 선형 (linear) 복잡도를 가진다. 그러나 사전에서 어떤 것을 찾을 때, 두배 크기의 사전의 경우에 사전을 한번 이상 더 열어봐야 하기 때문에 지수 (logarithmic) 복잡도를 가진다 (예를들어 정확하게 중간이라면 그 문제는 반으로 감소한다)
복잡도 이론으로 유명한 인물은 Juris Hartmanis, Richard Stearns, Stephen Cook, Richard Karp, Leonid Levin 등이 있다. 그들은 대부분 Alan Turing 상 을 수상했다. Cook 는 1971 년에 논문 "The Complexity of Theorem Proving Procedures"에서 NP-completeness 를 정의하고 boolean satisfiability problem 는 NP-complete 이다 라는 증명을 하였다. 그 논문으로 P 와 NP 복잡도가 같은 것인지 아닌지 (즉 NP = P 인지) 하는 컴퓨터 과학의 위대한 미해결 문제를 열어놓았고, 그것에 대한 대답을 발견하지 못하고 있다.
즉 'NP-complete 가 철저한 조사를 필요로 하는가 아니면 필요로하지 않는가?' 라는 문제이다. 그것을 다른 식으로 표현하면 다음과 같다. 즉, 세일즈맨의 여행 문제와 같은 문제들에 대해 가능한 경로들 가운데 오로지 어떤 작은 부분만을 검토하면서 그 문제를 해결할 수 있는 알고리즘 이 컴퓨터 과학의 역사를 변화시킬 것이란 이야기이다.
Juris Hartmanis 와 Richard Stearns 은 계산 복잡도 이론 분야의 기초를 놓은 논문 On the computational complexity of algorithms (1965) 을 발표했다. ........... (Wikipedia : Computational Complexity Theory)
복잡성 이론에서는 알고리즘의 속도가 다항식으로 표현되는 문제들을 묶어서 'P' 라고 부르고, 다항식으로 표현될 수 있는지 여부가 알려지지 않은 문제들을 묶어서 'NP' 라고 부른다. 여기서 P 는 Polynomial (다항식) 의 머리 글자고, NP 는 nondeterministic polynomial (비결정성 다항식) 의 머리 글자를 의미한다. 이때 NP 가 non-polynomial (비다항식) 을 의미하지 않는다는 사실에 유의할 필요가 있다. 다항식이 아니라는 사실과 다항식으로 표현되는지 여부가 아직 알려지지 않았다는 사실 사이에는 엄청난 차이가 존재하기 때문이다. 다항식으로 표현되는 알고리즘은 오늘날의 컴퓨터가 적당한 시간내에 해결할 수 있는 문제기 때문에 P 에 속한 문제들은 '쉬운' 문제들이고, NP 는 그와 반대로 '어려운' 문제를 의미한다.
복잡성 문제를 연구하는 학자들에게 가장 어려운 질문중의 하나는 바로 "NP 에 속하는 문제들이 궁극적으로는 모두 다항식, 즉 쉬운 알고리즘을 이용해서 해결될 수 있을까?" 라는 질문이다. 만약 그렇다면 NP 에 속한 문제나 P 에 속한 문제가 모두 종국에는 다항식으로 표현되기 때문에 'P = NP' 라는 등식이 성립하게 될 것이다. 하지만 NP 에 속하는 문제가 모두 다항식으로 해결될 수 있을지 여부를 파악하거나 증명하는 것이 너무나 어렵기 때문에 이 등식은 아직도 완전하게 입증되지 않은 어려운 명제 중의 하나로 통하고 있다.
한편 'NP-hard' 라고 불리는 문제들은 세일즈맨의 여행 문제처럼 모든 경우의 수를 전부 확인해보는 방법 이외에는 정확한 답을 구할 수 있는 뾰족한 수가 없는 문제들을 뜻한다. 어떤 문제가 NP 에 속하면서, 즉 다항식으로 표현될 수 있는지 여부가 알려지지 않았으면서 동시에 NP-hard 에 속한다면 ...... 그 문제는 'NP 완전 문제 (NP-complete)' 라고 부른다. .......
이러한 NP 완전 문제에 속하는 문제는 많다. 비밀번호를 깨뜨리기 위한 해킹 과정도 말하자면 이러한 NP 완전 문제에 속한다고 볼 수 있다. 비밀번호를 찾아내기 위한 알고리즘으로는 세일즈맨의 여행 문제에서 처럼 문자를 하나씩 대입해 보는 것 말고는 다른 뾰족한 방법이 없기 때문이다 ........... (임백준 2003)
term :
계산 복잡도 이론 (Computational Complexity Theory) 계산이론 (Theory of Computation) 다항식과 비결정다항식 (P and NP) 비결정 난해 (NP-hard) 비결정 완전 (NP-complete)
site :
Wikipedia : Computational Complexity Theory
Computational Complexity of Games & Puzzles : David Eppstein
paper :
video :
P vs. NP and the Computational Complexity Zoo : 2014/08/26
The Turing Computational Model : Juris Hartmanis, Richard Stearns, Stephen Cook, William Kahan : 2013/01/18
Computational Complexity : MIT : Erik Demaine, 2013/01/14