일반항과 점화식. 그리고 NP문제

 

수열의 표현 방식은 크게 두가지가 있다.

일반항(general term)이라는 결정적(deterministic) 함수 표현과 점화식(recurrence relation)이라는 재귀적(귀납적) 표현이 있겠다.

 

예를 들어 등차수열(arithmetic progression)의 경우 아래와 같이 표현이 가능하다.

$$ a_{n} = a + (n-1)d $$

하지만, 그 유명한 피보나치 수열(Fibonacci numbers)은 일반항 표현이 불가능하기에 아래와 같이 표현한다.

$$F_0 = 0$$

$$F_1 = 1$$

$$F_n = F_{n-1} + F_{n-2}$$

마지막 항을 살펴보면 n번째 수를 구하기 위해서는 n-1번까지의 수를 모두 알아야 한다는 것이 짐작 가능하다.

 

수열을 일반항으로 표현할 수 있다면 n번째 수를 구할 때 n이 아무리 크다 해도 정해진 방법과 시간을 통해 도출이 가능하다. 극단적으로 n이 (∞-1)이라고 해도 말이다(물론 이론적으로만).

하지만, 점화식으로만 표현 가능한 수열은 n이 커지면 커질수록 도출 방법과 시간이 선형적 혹은 기하급수적으로 커지게 된다.

 

이 것이 무엇을 뜻하냐면 점화식은 모두 NP문제라고 보면 된다는 것이다. 유명하다 못해 이제 고여버려 단순해 보이는 피보나치 수열 문제조차도 사실 NP문제라는 것이다. 왜냐하면 피보나치 수열에 대한 일반항이 현재까지는 존재하지 않기 때문이다. (만일 인류의 두뇌가 대폭 진화되어 일반항을 구하게 된다면 P문제로 발전하게 되겠지만, 뭐... 멸망이 더 빠를 듯.)