Polynomial time


어떠한 문제를 분석할 때, 주어진 문제가 상수(constant)로 표현되거나(e.g. O(1)), 선형(linear)적으로 증가하거나(e.g. O(n)), 변수 n에 붙은 지수가 상수로 표현될 때 우리는 이것을 다루기 쉬운(tractable) 문제라고 한다. 지수가 아무리 큰 수라고 하더라도 그것이 미리 정해진 상수라면 정해진 시간내에 계산해 낼 수 있기 때문이다. 우리는 이미 고등학교에서 배운대로 앞선 식들을 다항식(polynomial)이라고 부른다.
2n     3n3 + 4n    5n + n10    nlg n

이와 반대로 다항식으로 풀 수 없는 문제들이 있는데 복잡성 이론에서 이는 지수함수를 의미한다.(고등학교에서 지수함수의 반대는 로그함수였다.) 지수함수라는 것은 변수 옆에 붙은 지수가 미리 정해진 상수가 아니라 그 자신도 하나의 변수가 되는 것을 의미한다.
-2n     20.01n    2n-1    n!

이렇게 지수함수로 표현되는 문제들은 주어진 입력이 커질 수록 값도 기하급수적으로 늘어나게 된다. 이러한 문제들은 복잡성이론에서는 다루기 어려운(Intractable) 문제라고 부른다. 즉, 주어진 문제가 다항식이 아니라 지수함수로 표현되는 문제들은 어려운 문제다.

Polynomial time은 다항식 시간을 뜻하므로 다루기 쉬운 문제들을 해결하는 시간 의미한다. 입력 n의 값이 증가함에 따라 최대 nk로 표현되는 문제들을 해결하는 시간으로 빅오표기법으로 O(nk)(k는 상수)로 나타낸다. 결과적으로 polynomail time이 주어진 문제는 적절한 시간내에 그 문제를 해결할 수 있다는 말이므로 알고리즘이나 암호학 분야에서 자주 사용되고 그러한 문제들은 묶어서 'P(Polynomial)' 문제라고 부른다.

반면, 다항식으로 표현되지 않는 어려운 문제들은 'NP(Non-deterministic Polynomial)' 문제 라고 한다. NP가 'Non-polynomial'이 아니라 'Non-deterministic'라는 사실에 주목할 필요가 있다. 다항식으로 풀 수 없는 것이 아니라 아직 다항식으로 풀 수 있는지 결정되지 않았다는 것이다. 몇몇 수학자들은 이러한 NP 문제를 해결하기 위해 자신의 인생을 바치고 있기도 하다.
신고
Posted by Proneer

댓글을 달아 주세요


티스토리 툴바