속도를 분석할 때 n 이라는 변수에 붙은 지수가 1 이나 2 처럼 미리 정해진 값, 즉 상수(constant) 로 표현되는 경우에는 그 알고리즘을 '쉬운' 문제라고 간주한다. 지수의 값이 아무리 크다고 해도 그것이 미리 정해진 상수 값이라면 그 알고리즘은 컴퓨터가 적당한 시간 안에 계산해 낼 수 있는 쉬운 알고리즘에 해당하는 것이다. 이렇게 변수 위에 붙은 지수가 미리 정해진 상수인 수학 공식을 우리는 다항식 (polynomial) 이라고 부른다.
ex)2n³ x n² - 3
복잡성 이론에서 다항식의 반대말은 '지수 함수(exponential function)'다. 지수함수란 변수 위에 붙은 지수가 미리 정해져 있는 상수 값이 아니라 그 자신도 변수로 표현되는 함수를 의미한다.
ex)2^n, 3^n
복잡성(Complexity) 이론에서는 알고리즘의 속도가 다항식으로 표현되는 문제들을 묶어서 'P'라고 부르고, 다항식으로 표현될 수 있는지 여부가 알려지지 않은 문제들을 묶어서 'NP'라고 부른다. 여기서 P는 polynomial(다항식)의 머리 글자고, NP는 nondeterministic polynomial(비결정성 다항식)의 머리 글자를 의미한다.
이 때 NP가 none-polynomial(비다항식)을 의미하지 않는다는 사실에 유의할 필요가 있다. 다항식이 아니라는 사실과 다항식으로 표현되는지 여부가 아직 알려지지 않았다는 사실 사이에는 엄청난 차이가 존재하기 때문이다. 다항식으로 표현되는 알고리즘은 오늘날의 컴퓨터가 적당한 시간 내에 해결할 수 있는 문제기 때문에 P에 속한 문제들은 '쉬운' 문제들이고, NP는 그와 반대로 '어려운' 문제를 의미한다.
'NP-hard'라고 불리는 문제들은 세일즈맨의 여행 문제처럼 모든 경우의 수를 전부 확인해보는 방법 이외에는 정확한 답을 구할 수 있는 뾰족한 수가 없는 문제들을 뜻한다.
어떤 문제가 NP에 속하면서 즉, 다항식으로 표현될 수 있는지 여부가 알려지지 않았으면서 동시에 NP-hard에 속한다면, 즉 '무식한 힘'의 방법 말고 다른 절묘한 알고리즘이 알려져 있지 않다면 그 문제는 'NPC(NP-complete) 문제'라고 부른다.
컴퓨터 학자들과 프로그래머들은 대개 NP 완전 문제를 실용적인 관점에서 해결하기 위해서 진짜 정답을 찾기를 포기하는 대신 훨씬 적은 양의 계산을 통해서 정답에 가까운 값을 찾는 데 만족한다. 이러한 알고리즘은 근사 알고리즘(approximation algorithm) 혹은 발견적 알고리즘(heuristic algorithm)이라고 부른다. MST, 탐욕적 알고리즘, 평면 절단 방법 등은 모두 이러한 알고리즘의 예인데, 실전 프로그래밍의 세계에서는 이러한 근사 알고리즘이 생각보다 많이 사용된다.
복잡성 문제를 연구하는 학자들에게 가장 어려운 질문중의 하나는 바로 "NP에 속하는 문제들이 궁극적으로는 모두 다항식, 즉 쉬운 알고리즘을 이용해서 해결될 수 있을까?" 라는 질문이다. 만약 그렇다면 NP 에 속한 문제나 P 에 속한 문제가 모두 종국에는 다항식으로 표현되기 때문에 'P = NP' 라는 등식이 성립하게 될 것이다. 하지만 NP 에 속하는 문제가 모두 다항식으로 해결될 수 있을지 여부를 파악하거나 증명하는 것이 너무나 어렵기 때문에 이 등식은 아직도 완전하게 입증되지 않은 어려운 명제증의 하나로 통하고 있다.
term :
계산이론 (Theory of Computation)
계산 복잡도 이론 (Computational Complexity Theory)
비결정 완전 (NP-complete)
비결정 난해 (NP-hard)
다항식과 비결정다항식 (P and NP)
site :
Wikipedia : Complexity classes P and NP
paper :
복잡성 이론 : 임백준
