정말 흥미로운 문제가 있어 퍼왔습니다. 충분히 철게 여러 선생님들께서 관심 갖을 만한 문제라고 생각합니다. 게다가 상금도 100만 달러가 걸려 있다고 합니다. 이 문제에 관한 여러 선생님들의 사유 과정과 결론 도출 기대합니다.
컴퓨터 계산 시간에 관한 'P 대 NP(P vs NP Problem)' 문제도 있다. 'P 대 NP' 문제란 어떤 문제를 해결하는 알고리즘에서 답을 알고 있을 때와 없을 때 풀이에 시간 차이가 나는지 묻는 것을 말한다.
P를 다항식 시간에 풀 수 있는 문제 전체의 집합으로 하고, NP를 문제와 답이 주어지면 답이 맞는지 틀리는지 다항식 시간 안에 확인할 수 있는 문제 전체의 집합이라고 할 때, P⊆NP는 분명하다. 그렇다면 'P=NP일까 아니면 P≠NP일까' 하는 것이 바로 'P 대 NP' 문제이다. 이것은 미국의 클레이 수학연구소가 100만달러의 상금을 걸어 놓은 난문제 가운데 하나이다. [네이버 지식백과] 해밀턴폐쇄로문제 [Hamilton closed circuit] (두산백과)
아래 글은 P 대 NP 문제에 대해 컴퓨터 공학 분야에서 설명한 것으로 추정되는 글로 다른 글들에 비해 구체적으로 설명해 놓았기에, 컴퓨터 공학이나 알고리즘에 대해 문외한인 나에게도 이해가 쉽게 되기에 퍼왔습니다.
06/12/30 22:31(년/월/일 시:분)
과연 컴퓨터가 사람의 모든 일을 대신해줄 수 있을까? 그렇지는 않다는 얘기. 사람의 일에는 컴퓨터가 대신해줄 수 없는 부분이 분명히 존재한다.
이재하 교수님 - 알고리즘 수업 마지막 시간 중에서
어떤 문제들이 있잖아요, 알고리즘 문제들 전체가 이만큼이라고 하면, Divide-and-conquer(분할정복법)으로 풀 수 있는 문제가 요 정도 되고, Dynamic Programming(동적 프로그래밍)은 좀 많겠고, Greedy는 이 정도. 나머지는 대부분 잘 안 풀립니다. (웃음)
일부 잘 풀리는 문제들은 n, n², n³에 풀려서, 이런 애들을 polynomial-time(다항식 시간에 풀리는) 알고리즘이라고 부르죠. 이런 애들은 컴퓨터로 풀기가 좋은 문제들이에요. 이런 애들은 우리가 가져다 풀어서 쓰는 거구요.
나머지 애들은 우리가 polynomial-time인지 아닌지 아직 잘 모릅니다. 예를 들어서 n이 100자리 수라고 할 때, n의 약수를 하나만 구하라. 그러면 이게 잘 안 풀립니다. 시간 복잡도가 2ⁿ, 이런 문제들이 굉장히 많거든요. 바둑, 오목도 그렇고. polynomial-time 알고리즘을 아직 못 찾았어요. 하지만 없다고 장담도 못 합니다.
그런데 이쪽의 문제는 뭐냐하면요, 예를 들어
n=30 이면 2^30 (대략 10억) 연산
n=40 이면 2^40 (대략 1조) 연산
n=50 이면 2^50 (대략 1000조) 연산
이렇게 빨리빨리 늘어나거든요.
예를 들어 컴퓨터가 빨라져봤자 1초에 1억번 정도 연산을 하겠죠? 그러면 n=50 일때 1000만초, 대충 40일 정도 걸리겠죠. 굉장히 빠른 컴퓨턴데도. 지금 우리가 알고 있는 컴퓨터 중에 1초에 1억번 하는게 없잖아요. 그런데도 못 씁니다. 아무리 수퍼컴퓨터라고 해도 며칠, 몇달씩 걸리잖아요. 조금만 더 커져서 n=60, 70...씩 되면 몇 년, 몇 억년씩 걸리거든요. 그러니까 못 씁니다.
P: polynomial-time에 풀리는 문제들 (잘 풀림)
NP: 답의 후보가 주어지면, 그게 답인지 아닌지 체크하는데 polynomial-time이 걸리는 문제들 (잘 안 풀림)
지금까지 우리가 배운 거의 대부분의 문제들이 P 안에 들어있는 거구요, SAT(Satisfability) 같은 애는 P에 들어있는지 안 들어있는지 모르는 거죠. 이런 SAT 같은 문제가 있기 때문에 NP를 생각해낸 겁니다.
잠깐 심심풀이로 얘기하면요, NP 같은 건 사람들이 나중에 생각해낸 겁니다. P라는 클래스는 자연스러운 클래스니까, 사람들이 여기에 들어가면 프로그램을 짜서 문제를 풀 수 있다고 생각했거든요. 그런데 어떤 문제들이 거기에 들어갈지 안 들어갈지 모르는, 안 들어갈 것 같은 문제들이 많이 발견이 됐습니다. 그래서 그런 문제까지 들어갈 클래스를 만들어야 하거든요. 그래서 사람들이 생각해낸 게 NP죠.
이 NP는, 어... 이것도 좀 심오합니다. 이것의 배경을 약간 설명하면요, 사람들이 왜 이런 것을 생각해냈냐 하면, 물론 P에 안 들어가는 문제가 있으니까 NP를 생각한 건데, 왜 이런 식으로 생각했냐 하면,
NP가 의미하는 게 뭐냐 하면요, 어... 뭐라고 설명해야 되지... NP가 뭐의 약자냐 하면 Non-deterministic P, P앞에 Non-deterministic이 붙었어요. 이게 어떤 알고리즘을 말하는 거냐 하면, 추측을 굉장히 잘 하는 애를 말합니다. 추측하는 능력이 아주 탁월해요. 그런 알고리즘을 생각하는 겁니다. 그러니까...
지금부터 제가 하는 얘기는 약간 뜬 구름 잡는 얘긴데요. 여기에는 제가 생각하기에, 공학을 넘어서는 무언가가 있다, 이렇게 생각하거든요. (웃음) 심오한 게 있는 거죠.
사람들이 계산을 하는 과정을 컴퓨터로 만들려고 했잖아요? 그러다 보니까, 튜링(Alan Turing)은 어떻게 생각했냐 하면, 더하고 빼고 이런 연산을 할 수 있는 기계가 있으면, 즉 AND OR NOT을 할 수 있는 기계가 있으면 그걸로 숫자 계산을 다 할 수 있고, 그러면 그걸로 회로를 만들어서 덧셈도 할 수 있고, 곱셈도 할 수 있고, 덧셈과 곱셈을 할 수 있으면 그걸 막 빨리빨리 반복해서 다른 연산도 할 수 있다, 이렇게 생각했거든요.
그래서 어떤 정해진 계산을 굉장히 빨리 하는 애를 생각한 겁니다. 그런 컴퓨터를 생각했어요. 그래서 그 컴퓨터 안에서 우리가 덧셈도 할 수 있고, 곱셈도 할 수 있고, 금방 할 수 있거든요. 그런 연산들을 이용해서 우리가 polynomial-time에 풀 수 있는 문제들이 있는 거죠. 그런 집합을 정의했습니다.
앨런 튜링: 정해진 계산을 빨리 하는 컴퓨터를 만듬
P: 그 안에서 빨리빨리 풀 수 있는 문제들
그런데 거기 안 들어갈 것 같은 애들이 있거든요? 얘들은 어떤 애로는 들어가냐 하면... 답을 추측해요. 답을 추측한 다음에, 그게 맞는지 아닌지만 체크하는.
NP:
1. 답을 추측
2. 답인지 체크
이렇게 문제를 푸는 과정을 두 단계로 나눴습니다. 답이 뭘까 추측을 한 다음에, 그게 진짜 답인가 체크만 하고. 추측하고→체크하고. 사람이 이런 단계를 거친다는 거죠.
여기서 2번 단계는 컴퓨터가 잘 합니다. 정해진 계산으로 체크를 하는 거거든요. 길이가 얼마 이하냐, 이러면 길이 값만 쭉 더해주면 되잖아요? 그러면 체크를 간단히 할 수 있거든요.
그런데 1번 단계는 사실 컴퓨터가 어떻게 하는지 잘 모르는데요. 요 부분, 답을 추측하는 부분을 굉장히 잘 한다고 가정하는 겁니다. 그럴 때 polynomial-time에 풀 수 있는 문제. 그런 문제는, 추측은 잘 하니까, 추측은 그냥 거저 하는 거거든요. 그러면 답인지 체크만 하면 되니까, 그러면 그런 문제가 NP에 들어가게 되죠.
그런데 이게 인제... 에... 그래서 NP에 들어가는 문제에서는, 답의 후보까지가 주어진 겁니다. 얘가 추측을 한 거에요. 추측은 잘 했다고 치는 겁니다. 답의 후보가 탁 떠오른 거죠. 그래서 떠오른 답이 진짜 답인지만 체크하면 되는 겁니다. 그런 문제를 polynomial-time에 풀 수 있으면 NP에 들어간다, 라고 하는 거고.
P는 추측 과정 없이, 답을 다 풀어야 합니다. NP면 1번 단계가 공짜로 되는 거에요. 거저 되는 겁니다. 우리가 이런 걸 신탁(oracle)이라고 그러는 데요, 신전에 가서 물어봐서 답을 구하는 것처럼, 어떻게 할지 무당한테 가서 답을 구하던지 해서, 답의 후보가 되는 애를 하나 구한 거에요. 그러면 내가 걔를 가지고 체크만 할 수 있으면 됩니다. 1번 단계를 생략한 거에요. 거저 할 수 있다고 생각한 겁니다.
그래서 제가... 이상한 얘기를 하나 더 하면, 공자도 이런 생각을 했어요. 좀 웃기는데. 공자가 어떻게 얘기했냐 하면
사람이 바둑을 둘 때, 머리 속에 갑자기, "여기 놓으면 어떨까" 하는 생각이 떠오를 수가 있잖아요? 내가 여기 놓고, 쟤가 여기 놓으면, 내가 여기 놓고... 아 좋다. 또는 어? 이러면 안 된다. 이렇게 하잖아요.
사람이 머리 속에서 계속 무슨 생각인가가 계속 떠오르거든요. 여기가 좋아보인다 라던가, 여기 어떠냐? 이런 생각이 떠오르는데, 그건 뜬금없이 떠오릅니다. 뜬금없이 사람 머리속에 떠올라요. 그런 다음에 사람들이 어느 정도 훈련받은 과정으로 그게 정말 괜찮은지 체크를 해 보거든요.
사람의 머리 속엔 항상 두 가지 작용이 있는 거죠. 그래서 공자가 얘기한 걸로는, 하나는 쉽게 된다고 그랬고, 하나는 간결하게 된다고 그랬거든요.
1. 쉽게 된다
2. 간결하게 된다
하나는 쉽게 되요. 자기 머리 속에 여기가 좋아보인다 라는 생각이 탁 떠오르는데, 근거도 없고 뜬금없이 떠오르기 때문에, 힘들게 떠오르는 건 아니거든요.
그 떠오르고 나서 체크해 보는 과정은 자기가 공부를 많이 해가지구, 예를 들어 여기에 놓으면 죽나 사나 체크를 해 보잖아요? 그러면 우리가 여러 가능성들을 반복해서 빨리 빨리 해 보는 거죠. 이렇게 하면 되나? 저렇게 하면 되나? 여기 놨을 때 이렇게 이렇게 하면 되나? 해보는 거죠.
2번은 반복적으로 하는 과정입니다. 1번은 갑자기 무당의 머리 속에 떠오르거나 하는 것처럼 갑자기 뜬금없이 나타나는 거죠. 그거를 우리가 Non-deterministic하다고 하는 겁니다. 그래서 그런 두가지 과정 중에 1번을 거저 생긴다고 생각한 거구요.
동양에서, 공자는 1번이 굉장히 중요하다, 공자가 뭐라고 했냐 하면, 사람이 머리 속에 갑자기 떠오르는 생각은, 갑자기 맑은 날에 구름이 샤악 와서 비가 내리는 것처럼, 하늘의 변화막측한 현상을 닮았구요. 답인지 체크하는 것은, 봄에 씨 뿌리면 가을에 나고 그런 것처럼, 우리가 힘들게 하면 되는 그런 땅의 일이다.
사람의 머리 속에 하늘에 해당하는 부분과 땅에 해당하는 부분이 있는데, 1번은 정치고, 2번은 좀 더 단순한 노동이고, 단순한 지식이라고 나눴거든요.
그래서 여기서 비극이 시작된 건데, 2번은 쉽게 말하면 부엌 일이다, 이런 식으로 얘기했어요. 부엌에서 하는 일은 단순하고 시키는대로 하면 되는 일이고, 1번은 정치다, 정치는 나라가 어디로 나가야 될까 다소 뜬금없이 위에 있는 놈 머리에 생각이 떠오르는 거잖아요.
1. 하늘의 일
2. 땅의 일
그래서 하늘의 법칙을 닮아서 하는 건 정치나 철학이고, 땅의 법칙을 닮아서 하는 건 부엌 일이다. 그래서 사람들이 여자가 하는 일을 하찮은 일로, 과학, 기술 이런게 하찮은 일이 된 거죠.
기술이라는 게, 예를 들어 10자리 수 더하기 10자리 수를 어떻게 하냐, 열심히 하면 되는 게 사실이잖아요? 서양 애들은 그걸 100자리 수도 하고, 1000자리 수도 하고, 계속 하고 싶어했거든요. 그런데 동양에서는 그런 걸 부엌 일이다, 그래서 별로 중요시 안 했거든요.
2번은 배울 수 있다. 공자가 2번은 가르칠 수도 있고 배울 수도 있다고 했거든요. 왜냐하면 간단하게 단순하게 하는 것이기 때문에 가르치기도 쉽고, 가르치면 또 배워서 할 수도 있고.
그런데 1번은 가르칠 수가 없어요. 내가 좋은 생각이 떠오른다고 해서, 내 자식한테 좋은 생각이 떠오르도록 가르칠 순 없잖아요. 이쪽은 별로 잘 가르쳐줄 수가 없는 겁니다. 굉장히 고상한 걸로, 경지가 있는 걸로 말이 된 거죠.
1. 정치, 철학. 배울 수 없다. - 동양
2. 과학, 기술. 배울 수 있다. (단순 반복) - 서양
동양에서는 1번은 중요시 하면서, 2번을 하찮게 생각했습니다. 단순 반복이거든요. 그런 하여튼... 공자가 이런 데 크게 관심이 있었다는 거구요.
그런데 컴퓨터 하는 사람들이 쉽게 안 풀리는 문제를 생각해 보니까, 답을 예측만 잘 해주면 쉽게 풀리거든요. 체크는 잘 하잖아요.
그래서 이런 문제를 생각한 거에요. 머리속에 탁 떠오르는, 뜬금없이 떠오르는 걸 잘 하는 애. 굉장히 이상적인 경웁니다. 현실적인 게 아니라, 이상적인 애에요. 이상적인 컴퓨팅 기계거든요.
NP: 이상적인 컴퓨팅 기계
P: 현실적인 컴퓨팅 기계
좋은 생각이 머리속에 탁 떠오를 때, 그런 애에 대해서 답을 체크하는 것만 한다고 하면 금방 할 수 있는. 정확히 2번 일에만 한정을 시킨 거죠. 공자가 부엌 일이라고 한 곳에 한정을 시켜서, 그걸 polynomial-time에 할 수 있으면 NP 문제라고 한 거죠.
(이어진 내용)
- P와 NP가 한 끝 차이로 매우 비슷하다. 그런데도 안 풀린다.
- NP는 굉장히 오랬동안 풀어봤지만, 잘 안 풀린다. 그렇다고 증명할 수도 없다.
- 그래서 증명하는 대신, 잘 안 풀릴 가능성이 높다는 것을 보여준다. NP 문제들은 서로 엮여있다. (하나가 풀리면 나머지도 풀림. 공동 운명체)
- 엮인 문제들을 NP-complete라고 한다. (NP-complete는 '포기'와 동의어. 왠만해선 안 풀리니까)
- 그럴 때 정면이 안 되면 측면으로 돌파한다. Heuristic (대충 답을 구하는 것. 증명할 수는 없지만 대충은 잘 풀린다.)
제 생각에 여기서 제일 재미있는 부분은, NP 문제들이 공동 운명체로 묶여있다는 거죠.
이 문제들이 polynomial-time에 풀리냐 안 풀리냐 하는 건 굉장히 중요한 문젭니다. 아까도 얘기했지만, 풀리게 되면 암호 시스템을 싸그리 다 바꿔야 하거든요. 바꿔야 할 뿐만 아니라, 특별히 바꿀 방법이 없습니다. 암호 시스템은 전적으로 얘네들이 polynomial-time에 안 풀릴 거라는 거에 기반하고 있거든요. RSA, Public-Key 같은 거요. 그것 뿐만 아니라, 좋아지는 애들도 많겠죠.
중요한 문제죠. 그런데 사람들이 답을 모르니까, 이것들을 공동 운명체로 묶은 거에요. 여기(NP-complete)에 있는 문제들이 많아지면 많아질수록, 잘 안 될거라는 증거를 주는 거죠. 물론 전부 한번에 풀릴 가능성도 높아지는 거고. 그런 식으로 엮여 있습니다.
이제 끝났는데요. P=NP냐, 수학자들이 21세기에 풀어야 되는 문제를 7가지를 선정했는데, 백만불이 걸려 있죠. 얼마 전에 하나 풀렸잖아요? 푸앙 카레 가설. 그것보다 P=NP 문제가 1번입니다.
P=NP 문제는 수학자들이 만든 문제가 아니라, 컴퓨터 하는 사람들이 만든 문젭니다. 저 문제가 생길때 까지는 컴퓨터 하는 사람들은 수학자들에게 놀림을 당했어요.
수학자들이 왜 놀렸냐 하면, 수학에서는 어떤 생각이 있냐 하면, 무한을 다루지 않으면 별로 아름답지 않다. 유한한 게 몇 개나 있겠느냐, 무한한 게 훨씬 많은데. 어떻게 유한한 걸 다루냐. 그래서 컴퓨터 하는 사람들이 대접을 별로 못 받았습니다.
그런데 P=NP 문제가 나오고, NP 문제가 있다, NP 문제들이 이렇게 많은데, 얘가 polynomial-time에 되냐 안 되냐, 그리고 그게 추측하고 검증하는 것과 그냥 계산하는 거와의 관계거든요. 그러니까 굉장히 철학적인 문제죠. 사람들이 체스를 자동으로 두고 싶어할 때부터, 지능을 가지고 싶어할 때부터 걸쳐 있던 문제와 닿아 있고, 여러 가지 문제와 닿아 있거든요.
그래서 수학자들 중에 유명한 애들이, "그러면 내가 가서 해결해주고 오겠다" 이러고서 우리 동네 왔다가, 한 10년 동안 못 풀고 개기고 있으니까, 다른 애들이 또 온 거죠. 와가지고 해 보니까 자기들이 거의 10년동안 수학자들 중에 굉장히 유명한, 거의 톱 클래스의 수학자들이 들러 붙어서 하고 있는데 못 하고 있거든요.
그래서 자기들이 급기야 제일 중요한 문제로 뽑았습니다. 자기들이 만든 문제가 아니고, 컴퓨터가 만든 문제에요. 그러니까 컴퓨터 쪽이 약간 대접을 받는 거죠. 그쪽 동네에 가면 흥미로운 문제니까. 그 전까지는 찬밥 대접을 받았습니다.
요즘은 수학하는 사람들 만나면 P=NP 문제를 자기들한테 설명을 좀 해달라고 하고. 많은 수학자들이 관심을 가지고 있습니다.
가장 잔머리의 극치거든요. 이런 식으로 엮는 방법을 생각한다는 거 자체가.
펌글
글쓰기