P VS NP, 다항시간, 지수시간, 결정적 알고리즘, 비결정적 알고리즘

이번 글에서는 P와 NP에 대해 다뤄 보도록 하겠습니다. 솔직히 저도 한글로 되어있던지, 영어로 되어있는 글이든 읽으면서 도대체 무슨 말인가라고 할 정도로 이해가 되지 않더군요. 자꾸 반복해 읽어도 조금 이해가 되는 듯 말 듯 여전히 어려운 개념이지만 같이 공부해 봅시다. 

 

P vs NP

 

• 만약 다항식 시간(polynomial time) 내 결정적 알고리즘(a deterministic algorithm)으로 해결할 수 있는 컴퓨터적인 문제(Computional problem) x 가 있다면  x 는 P의 클래스 안에 있다. 
• 만약 다항식 시간(polynomial time) 내 비결정적 알고리즘(a non-deterministic algorithm)으로 해결할 수 있는 컴퓨터적인 문제(Computional problem) x 가 있다면  x는 NP의 클래스 안에 있다.

기존의 알려져 있는 P와 NP의 정의입니다. 도대체 다항식 시간은 무엇이며 결정적, 비결정적 알고리즘은 또 무엇인지를 이해하지 못하면 무슨 말인지 이해하기 어려울 것입니다. 그래서 이것들의 의미를 알려보려 합니다.

 

다항식 시간(Polynomial time)

• 단순히 말해서 다룰 수 있는 시간 내에 해결가능하다는 의미입니다. 이에 반대되는 의미는 지수시간(exponential time)으로 시간내 해결 불가능한 다루기 힘든 경우라고 합니다. 예를 들어 다항 시간인 O(n^2)와 지수 시간인 O(2^n)를 비교해 봅시다. n 이 10일 때 전자는 10^2 = 100, 후자는 2^10 = 1024입니다. 만약 n = 20이라고 한다면 전자는 20^2는 400 후자는 2^20은 1048576입니다. 전자는 겨우 300이 커졌는데 후자는 비교해 보기도 어려울 만큼 커져버렸습니다. 그리고 여기에 n이 1씩만 커져도 후자의 경우 엄청난 비율로 숫자가 커져버립니다. 한마디로 감당할 수 없는 숫자인 것이죠. 

결정적 알고리즘(a deterministic algorithm)  

• 특정한 값을 입력하면 그에 따라 정해진 값이 나오는 것을 결정적 알고리즘이라고 합니다. 수학공식이 가장 대표적인 예입니다. f(x) = x+1이라고 한다면 f(1) = 2, f(2) =3, f(k) = k+1으로 정해진대로 결괏값이 나오게 됩니다.

비결정적 알고리즘(a non-deterministic algorithm)

• 동일한 값을 입력해도 다른 결과를 출력할 수 있다고 정의할 수 있습니다. 

 

q0에서 0을 입력했을 때 유일한 값이 아닌  q1,  q2 2가지 결과를 얻을 수 있습니다. 

이해하기 난해합니다 같은 값을 입력했는데 다른 결과를 출력하는 것이 무엇이 있는지 잘 이해되지 않는데요. 

 

좀 현실적인 예를 찾아보려고 곰곰이 생각해보다 한 가지 예를 들어 보려 합니다. 틀릴 수도 있으니 너그러이 봐주시기 바랍니다. 

 

 

 

 

 

 

위 그림은 볼링 레인입니다. 그리고 한 명의 플레이어가 있습니다. 이 플레이어는 기계와 같아서 매번 똑같은 구속과 회전수를 가지고 원하는 위치에 볼을 굴릴 수 있습니다. 이 플레이어가 왼쪽에서 첫 번째 점에 볼을 굴려 가운데 화살표를 시속 30km/h로 분당 회전수 500으로 통과하면 1, 3번 핀을 맞춰 스트라이크를 칠 수 있습니다. 하지만 10번을 던졌는데 스트라이크는 7번이고 3번은 10번 핀이 남아버렸습니다.

 

만약 던지는 족족 스트라이크가 나왔다면 이는 분명 결정적 알고리즘일 것입니다. 그런데 이것이 비결정적 알고리즘이 되어버린 이유는 위키피디아를 참고해서  

 

어떤 알고리즘이 비결정론적으로 작동하게 하는 데는 여러 방법이 있다.

• 입력 이외의 외부 상태를 알고리즘에 적용함 [2]
• 알고리즘이 시간에 민감하게 동작함 [3]
• 하드웨어의 오류를 이용하여 알고리즘 진행과정을 예상할 수 없는 방식으로 변화시키는 방법

2. 예: 사용자의 입력, 전역 변수, 하드웨어 타이머 값, 난수 등을 알고리즘 진행과정에 입력으로 넣는 방법.

3. 예: 여러 개의 프로세서가 동시에 같은 메모리에 값을 쓰려고 하는 경우, 각 프로세서가 어떤 순서로 썼는지에 따라 결괏값이 달라진다.

 

이 중 '입력 이외의 외부 상태를 알고리즘에 적용함 [2]'을 이용해 설명해 보고자 합니다.

 

볼링 레인에는 오일이 깔려 있습니다. 볼링은 이 오일을 이용해 볼을 조절할 수 있습니다. 하지만 공이 한번 지나가는 구간에는 공의 마찰에 의해 오일이 미묘하게 뭉개져 볼의 움직임에 변화를 준다는 사실을 미리 알아야 합니다. 

 

각 플레이어들의 어떻게 공을 던지냐는 플레이어마다 원하는 대로 변화시킬 수 있기에 매개변수이고 모든 플레이어들에게 공통으로 적용되는 오일 패턴은 전역 변수라고 할 수 있습니다. 다시 말해서 이 기계적 플레이어가 던질 때마다 오일 패턴이 미묘하게 변하게 되고 이 전역 변수는 알고리즘에 영향을 미치게 됨으로써 매번 똑같이 굴림에도 불구하여도 다른 결과를 만들어 내게 되는 것입니다. 

 

이번 글에서 P와 NP에 대해 이해하기 앞서 다항식 시간, 지수 시간, 결정적 알고리즘, 비결정적 알고리즘에 대해 설명하고자 했습니다. 특히나 비결정적 알고리즘에 대해 예를 통해 설명하려 했는데 이를 이해하기 위해 볼링에 대해 알아야 한다는 아이러니 하게 되어버렸습니다. 다음 글에는 NP Hard, NP Complete에 대해 설명해 보려 합니다. 

 

참조

위키피디아