실제 여행하는 외판원의 알고리즘 모습
10개 도시를 최단거리로 여행하는 법
지금까지 이짐 검색과 퀵정렬 등을 알아봤는데 보통은 선형(N)의 복잡도, 일의 양이 데이터 양에 정비례하며 퀵 정렬 같은 경우는 NlogN의 복잡도를 갖는데 N보다는 효율이 낮지만 일의 양이 정비례하지 않으므로 효과적이다.
N의 2승 복잡도는 일의 양이 너무 빨리 늘어나서 실행이 어렵거나 불가능하다. 3승의 경우는 전문가들만 관심을 가지는 정도인데, 특이할 사항으로는 지수(exponential)복잡도로 2의 N승의 비율로 증가한다. 일의 양이 유난히 빠르게 증가하는데 이는 모든 가능한 경우를 하나씩 시도해 봐야만 하는 상황에서 발생한다.
반대로 이런 알고리즘이 유용한 경우가 있ㅇ는데, 암호기법에 사용되는 알고리즘이다. 이때 암호를 알지 않고서는 문제를 바로 푸는 일이 계산산 실행 불가능할 정도로 큰 N을 사용한다.
이렇게 보면 쉬운 문제와 어려운 문제를 구별하는 법을 알 수 있다. 복잡도 면에서 "다항"인 문제는 쉬운 문제이다.
*다항(Polynomial)
여기서는 단순히 N의 2승이나 N의3승같은 거듭제곱 꼴로 생각하는 게 낫다
이를 다항의 알파벳인 P라고 부르는데, 지수 알고리즘이 필요한 문제는 NP문제라고 한다. NP문제는 해결책을 빨리 찾을 수는 없지만, 어떤 해결책을 알고 있다면 그것이 맞는지는 빨리 입증할수 있다.비 결정적 다항(Nondeterministic Plolynomial)을 뜻하며 그 알고리즘에 의해 다항 시간 내에 새결할 수 있다.
이는 굉장히 기술적이지만 실제 응용 예시로는 여행하는 외판원 문제(traveling salesman problem)이다. 이 문제에서 외판원은 자신이 사는 도시에서 출발에 어떤 순서로든 다른 도시를 모두 방문하고 나서 다시 풀발점으로 돌아와야 한다. 여기서 목표는 각 도시를 정확히 한 번씩 방문하고, 전체 여행한 거리를 최소로 만드는 것이다. 이 문제는 통학버스, 쓰레기차가 다니는 경로를 효율적으로 만드는 일과 아이디어가 같다.
아직 까지 최단 경로를 찾는 방법은 모든 가능한 경로를 시도해 보는 것 밖에 없으며, 예전보다 기발해졌을 뿐이다.
이는 알고리즘을 연구하는 사람들에게 좌절감을 준다. 문제가 본질적으로 난해해서인지, 아니면 우릭 ㅏ덜 똑똑해서 아직 해결책을 알아내지 못한 것인지는 모르지만, 오늘날에는 "본질적으로 난해하기 때문"인 것으로 의견이 기울고 있다.
P 와 NP가 같은지 밝히는 문제는 2000년대 클레이 수학 연구소에서 상금을 걸은 일곱가지 미해결 문제 중 하나에 해당하며 하나 당 100만달러의 상금이 걸려있다.
우리가 이런 복잡도를 다룰 때 명심해야할 점은 복잡도란 대부분 최악의 경우에 대한 것이며 보통은 최악의 경우까지 가지 않는다. 다시 말해, 어떤 문제는 답을 계산하는데 극하의 시간이 필요하겠지만, 모든 문제를 그렇게 난해하게 접근할 필요는 없다. 도시를 방문하는 외판원도 근사치만 구하는 것으로도 충분하며 완전히 최적인 해법을 구할 필요는 없다.
물론 반대로 암호시스템의 경우는 정말로 풀기 어려울 것이라는 믿은에 기반한다. 그래서 단기적으로는 실효성이 없어보이는 공격이더라도, 그 공격에 반격해 내는 것이 중요하다.
