그래서 P-NP 문제가 뭔데?
- 편집팀
- 2월 16일
- 6분 분량
현대 이론 컴퓨터 과학, 수학계의 주요 관심사이자 밀레니엄 문제인 ‘P-NP 문제’를 이해해보자! 친숙하고 재밌는 스토리탤링과 일상에서 쉽게 접할 수 있는 예시들로 구성되어 있어 부담 없이 익힐 수 있을 것이다. 지적인 티가 팍팍나는 미래의 당신이 기대되지 않는가?!
P-NP 문제 첫 걸음
독자 분께서는 간단한 소설 속으로 들어가서 이 훌륭한 이야기를 이해하실 것이다. 당신은 당신의 친구와 함께 모험을 떠나기로 한다.(재미있는 친구와 함께 가도록 하자!) 목적은 딱히 없다. 그냥 나들이라고 하는 편이 더 나으려나. 아무튼, 모험을 떠난 친구와 당신은 첫 번째 목적지인 마을을 향해 가려 들밭을 지나고 있다. 거리를 걷던 당신과 당신 친구는 심심한 나머지 서로에게 사칙연산 문제를 내기 시작했다.(아무튼 그렇다)
당신이 먼저 친구에게 질문했다.
‘10 더하기 7이 뭐게?’
친구는 1초도 채 안 걸려 당연하다는 듯이 대답한다.
‘너무 쉬운 거 아냐? 당연히 17이지.’
그러자 당신은 한번 더 친구에게 질문한다.
‘148 더하기 28이 뭐게?’
친구는 3초 정도 고민하더니 자신 있게 답한다.
‘수준이 똑같잖아! 176이지.’
그러자 당신은 또다시! 친구에게 질문한다.
‘164923655586 더하기 28925751185’이 뭐게?’
친구는 듣자마자 고개를 절레절레 저으며 대답한다,
‘아니 그걸 어떻게 암산으로 계산해. 1분 동안 적어가며 계산해도 맞출까 말까인데.’
친구는 말도 안되는 문제를 듣고 기분이 뾰로통해진 듯하다. 이후 조용해져서 걷기를 1분, 갑자기 당신의 친구는 ‘193849406771’이라고 외친다! ‘알고 보니 속으로 몰래 암산이라도 하고 있었나 보군.’ 당신도 답을 몰라 계산해봐야 하나 하고 있던 찰나, 정답이라고 대답해주지도 않았는데 의기양양해진 친구는 역으로 당신에게 물어본다.
‘이번엔 내 차례야. 7곱하기 9는?’
당신은 학창시절 배운 구구단을 떠올리며 자신 있게 대답한다.
‘63이지. 너무 쉬운 거 아닌가’
그러자 당신 친구는 의미심장한 미소를 짓는다. 그리고 3분 뒤 대뜸, 질문한다.
‘36585 곱하기 32895는?’
오우 마이 갓. 딱봐도 엄청난 수의 계산이 필요해 보인다. 암산을 해보려 하지만 머릿속에서 숫자들이 떠다니며 뒤죽박죽되고 아무 생각도 나지 않는다. 아쉽게도 포기해야 할 것 같다. 옆에서 모른다고 놀리며 깐족거리는 친구를 봐줘서라도 말이다.
... ...
조금 걷다 보니 벌써 오후 9시경이 되었다. 당신과 친구는 숙소에서 잠시 묵기로 한다. 숙소에 들어와 확인한 침실은 완벽했다. 조용하고 어두웠으며 가장 중요한 침대는... 아주 푹신했다! 당신은 ‘이건 못 참지’라며 침대에 다이빙한다. 그리고는... 1초 만에 잠이 들었다.
아침에 일어난 당신은 당신 앞의 작은 꼬마 로봇을 주시하고 있다. 어린아이의 형상에 뒤통수에 작은 철골이 튀어나온 이 로봇이 어디서 왔는지, 왜 내 침대에서 뛰어놀고 있는지 의문일 따름이다. 당신의 친구는 아직 깨지 않은 듯한데, 로봇이 친구 얼굴에 바싹 붙어 있는 것이 어째 불안하다. 그리고 5분 뒤 이상한 낌새에 눈을 뜬 당신의 친구는 소리를 지르기 시작했다.
‘으아아아아아아아아아아아아아아아아---아악’
한바탕 난리가 지나가고 남은 것은 3분간 쉬지 않고 소리를 질러대 나가버린 친구의 성대와 로봇의 간단한 자기소개뿐이었다. 대충 상황을 파악해보니 로봇은 원래 정처 없이 여러 군데를 돌아다니는 것이 취미인 듯하다.(진짜로 자기소개는 그것이 다였다!) 여전히 경계 중인 당신의 쫄보 친구를 두고 당신은 로봇과 대화를 시도한다.
‘우리한테는 왜 온 거야?’
‘당신들-- 사칙연산 얘기-- 재밌어 보였다-- 삐리리리--’
가끔 끊겨 들려 듣기는 힘들었지만, 당신은 두 가지 정보를 알아낼 수 있었다. 첫 번째, 이 소름돋는 로봇이 우리를 계속 따라오고 있었다는 것. 두 번째, 이 망할 사칙연산 퀴즈 참여자가 한 명 더 늘었다는 것! 나빠 보일 것도 없었기에 당신과 친구는 로봇과 같이 여행을 이어나가기로 한다.
척척박사 로봇과 함께 다니기 시작한 이후 당신은 신기한 것을 알게 되었다. 가령, ‘10 더하기 11은 뭐야?’라고 질문했을 때, 우리의 꼬마 박사님은 몇 안 되는 0과 1만으로 몇 나노초 만에 작업을 끝낸 뒤, ‘21’을 자신 있게 답으로 내놓는다. 그런데 여기서 놀라운 점은 ‘32765926592 더하기 1862410597은 뭐야?’라고 질문해도 ‘34628337189-- 삐리리리--’하며 마찬가지로 몇 나노초 만에 정답을 내놓는다는 것이다. 7 곱하기 9도, 28194712984 곱하기 328672049860도 곧바로 대답을 내놓았다!(물론 그게 정답인지는 확인할 방법이 없다. 믿거나 말거나) 항상 암산을 시작하려 하자마자 답을 내놓는 로봇은 참 신기하면서도 의문스러웠다.
‘헤이 로봇, 너는 모든 것을 다 순식간에 계산할 수 있어?’
그러자 로봇은 대답한다.
‘다항 시간 내 연산이라면 거의 다?’
다항 시간?
이제 머리를 조금 써야 할 때가 왔다! 우선 당신의 머릿속에 생긴 커다란 물음표부터 해결해야 할 듯하다. ‘다항 시간’이 무엇일까? 정의는 다음과 같다.
이렇게 적어놓으니 무슨 소리인지 하나도 모르겠다. 그러나 걱정할 필요는 없다. 하나하나 살펴볼 거니까.
먼저 ‘어떠한 문제를 계산하는 데에 걸리는 시간’이 무엇인지부터 알아야 한다. 걸리는 시간이라... 위의 대화 내용을 떠올려보자. 당신의 친구는 ‘7+11’을 계산하는 데에 몇초가 걸렸는가? 그렇다. 1초도 채 되지 않아 대답했다. 그렇다면 ‘164923655586+28925751185’은? 대략 1분 만에 맞춘 듯하다. 여기서 우리는 한가지 추측을 할 수 있다.
‘‘7 더하기 11’ 문제를 계산하는 데에 걸리는 시간은 1초, ‘148 더하기 28’ 문제를 계산하는 데에도 1초, ‘164923655586 더하기 28925751185’ 문제를 계산하는 데에 걸리는 시간은 1분’
과연 이것이 합당한 추론일까? 결론부터 말하자면 그렇지 않다. ‘다항 시간’의 정의에서의 ‘어떤 문제를 계산하는 데에 걸리는 시간’은 컴퓨터 기준으로 맞추어져 있다. 즉, 사람이 계산할 때 걸리는 시간이 기준이 아니라는 것이다. 우리의 꼬마 로봇이 ‘10 더하기 11’, ‘32765926592 더하기 1862410597’, ‘7 곱하기 9’, ‘28194712984 곱하기 328672049860’을 모두 몇 나노초 만에 계산한 것을 보면 이제껏 소개된 모든 연산 문제는 계산하는 데에 몇 나노초면 충분하다는 것을 알 수 있다. 더 정확하게는, 컴퓨터는 모든 사칙연산을 ‘한 번’의 연산으로 치며, 이 작업은 단 ‘1억분의 1초’면 충분하다. 예시로, ‘1+2+3+4+5+6+7+8+9+10’은 10번의 연산횟수가 필요하므로 ‘1000만 분의 1초’면 충분할 것이다.
‘계산하는 데에 걸리는 시간’을 대략 이해했으니, 이제 ‘M(n)’이 무엇인가를 살펴보고자 한다. M(n)은 문제의 크기 n에 관한 계산 시간 함수이다.(문제의 크기는 다루어야 할 자료의 개수라고 이해하면 편하다. 가령, 10개의 숫자를 덧셈할 때는 문제의 크기가 10이 된다.) 즉, 숫자를 덧셈하는 작업은 M(n)=n*(연산횟수당 시간)이 될 것이다. 다항식 함수는 말 그대로 다항식 꼴의 함수를 의미한다.
예시로 확인해보자. 임의의 n개 숫자 배열이 있을 때, 각각의 숫자 사이에 + 또는 -를 넣어 계산 값이 지정된 숫자 K가 되도록 할 수 있는지 확인하려 한다. 이 상황은 다항 시간 내에 해결될 수 있을까? 5분 정도 충분히 고민해보도록 한다.
5분 정도 고민한 결과, 다음과 같은 의문을 떠올렸다면 아주 훌륭하다.
‘처음에 다 +로 채워넣었더니 계산 값으로 K가 나왔으면 n*(연산 당 시간, 앞으로는 P라고 표기)이면 충분한 것 아니야?’, ‘그런데 또 끝까지 못 찾으면
시간이 필요하네’
전자의 경우 ‘n*P’와 같은 다항식 꼴 내에 완료되지만, 후자는 ‘(2^n)*n*P’와 같이 다항식 꼴 보다 큰 시간이 필요하다. (지수함수는 n이 커졌을 때, 다항식보다 충분히 커지게 할 수 있다.) 여기서 우리는 한번 더 정의를 명확하게 할 필요가 있다. ‘어떤 문제를 계산하는 데에 걸리는 시간’은 항상 최악의 경우를 가정한다. 즉, 여기서는 이 문제를 해결할 때 걸리는 시간이 ‘(2^n)*n*P’로 표현된다. 따라서 이 문제는 다항 시간 내에 해결될 수 없다.
P 문제와 NP 문제
이제 P-NP 문제를 이해하기까지 단 한 걸음만이 남았다! P-NP 문제는 ‘P 문제’와 ‘NP 문제’ 사이의 관계를 다룬다. 고로 ‘P 문제’와 ‘NP 문제’가 무엇인지 먼저 이해할 필요가 있다.
‘결정 문제’에 대해서 들어본 적이 있는가? 이름은 거창하지만 말 그대로 답이 진릿값, T or F로 결정되는 문제를 말한다. 예를 들어 a는 b와 서로소인가?’는 결정 문제이지만, ‘a의 모든 약수를 구하라’와 같은 질문은 결정 문제가 아니다. P 문제와 NP 문제는 모두 결정 문제에 속하며, 우리가 잘 이해한 ‘다항 시간’을 사용하여 잘 정의할 수 있다.
P 문제: 다항식(Polynomial) 시간 이내에 그 문제의 답을 계산해낼 수 있는 알고리즘이 존재하는 문제
NP 문제: 문제를 푸는 각 단계에서 여러 가지의 가능성을 동시에 고려할 수 있는 비결정적 알고리즘(non-deterministic algorithm)으로, 다항 시간 내에 문제를 해결할 수 있는 문제
P 문제의 정의는 무리 없이 이해할 수 있을 듯한데, NP 문제의 정의가 다소 아리송하다. 우리는 NP 문제를 다음과 같이 문제 검산의 측면에서 정의할 수도 있다.
NP 문제: 어떤 결정 문제의 답이 T일 때, 그 문제의 답이 T라는 것을 입증하는 '힌트'가 주어지면, 그 힌트를 사용해서 그 문제의 답이 정말로 T라는 것을 다항 시간 이내에 확인할 수 있는 문제
결론적으로, P 문제는 다항 시간 이내에 문제의 답을 계산할 수 있는가? 존재성의 문제이고, NP 문제는 다항 시간 이내에 문제를 해결할 수 있는가? 검산의 문제이다. NP 문제는 어떤 문제가 주어졌을 때 다항 시간 내 해결 가능한 알고리즘이 존재하는지에 대해서는 관심이 없다. 예를 들어 정수 n개로 이루어진 집합이 주어질 때, 원소의 합이 0이 되는 부분집합을 찾는 다항 시간 내 알고리즘은 아직 밝혀지지 않았다. 그러나 우리는 답으로 특정 집합이 주어졌을 때 그 집합이 부분집합인지, 원소의 총 합이 0인지는 다항 시간 내에 손쉽게 확인할 수 있다. 즉, 위의 문제는 확실히 NP 문제이지만 P 문제인지는 모른다.
잘 이해했다면, 다음과 같은 예시가 P 문제인지, NP 문제인지 잘 판단할 수 있을 것이다.
‘임의의 n개 숫자 배열이 있을 때, 각각의 숫자 사이에 + 또는 -를 넣어 계산 값이 지정된 숫자 K가 되도록 할 수 있는가?’
그렇다! 아까 예시로 제시한 문제이다.
정답은 ‘NP 문제인 것은 확실하나, P 문제인 것은 알 수 없다.’ 이다.
P-NP 문제
이제 드디어 ‘P-NP 문제’를 이해하기 위한 모든 준비가 완료되었다! 앞의 ‘P 문제와 NP 문제’까지 완벽하게 이해했다면, 황당할 정도로 설명할 것이 없다.
‘P-NP 문제: P 집합과 NP 집합은 같은가?’
P, NP, NP complete, NP hard
P-NP 문제는 사실 거의 결론이 결정된 문제가 다름없다. 대부분의 수학자는 P 집합과 NP 집합이 다를 것이라고 생각한다. 증명 방법이 밝혀지지 않아 해결되지 않고 있다고 해도 과언이 아닐 것이다. 하지만 중요한 점은 그 증명은 80억 인구 중 누구도 해내지 못하고 있다는 것이다. 언제 쯤 P-NP 문제가 해결될까?
기사를 마치며
본 기사에서는 P-NP 문제의 이해를 위해 NP 문제의 정확한 정의(NTM, Non-deterministic Turing Machine을 활용)도 사용하지 않았고, 시간 복잡도, P, NP, NP complete, NP hard등의 주요 개념도 설명하지 않았습니다. 엄밀하지 않은 부분이 다수이며, 미숙한 점이 많음을 미리 사과드립니다. 감사합니다:)
박정현 학생기자 | Mathematics & Computer science | 지식더하기
참고자료
[1] https://namu.wiki/w/P-NP%20%EB%AC%B8%EC%A0%9C
[2] https://m.dongascience.com/news.php?idx=19873
첨부 이미지 출처
[1] https://velog.io/@hyeonseop/P%EC%99%80-NP
[2] https://all-young.tistory.com/6
[3] https://ko.wikipedia.org/wiki/NP-%EC%99%84%EC%A0%84
Comments