P-NP 문제

어려운 문제를 쉽게 풀 수는 없을까?

어려운 문제를 스스로 해결해 본 적이 있나요? 몇 시간이 걸리고, 길게는 며칠이 걸려서 한 문제를 해결하곤 하죠.

그때의 짜릿함과 성취감은 이루 말할 수 없어요. 마치 하늘을 날아갈 듯한 느낌이죠.

하지만 늘상 문제가 해결되지는 않는 법. 우리는 그럴 때 마다 이런 생각을 하곤 해요.

“어려운 문제를 쉽게 풀 수는 없을까?”

비슷한 생각을 했던 수학자가 한 질문을 던졌어요.

쉽게 풀 수 있는 문제들을 모아 둔 P집합이 있어요. 그리고, 쉽게 검산할 수 있는 NP 집합이 있고요.

이때, P 집합과 NP 집합은 같을까요? 이 문제가 바로 P-NP 문제예요.

여기서 말하는 문제는 일반적인 문제가 아닌 ‘True/False’로 나타내는 결정문제만을 말해요.

(※ 쉬운 이해를 위한 아주 간단한 설명이에요. 자세한 설명은 인터넷을 참고해주세요!)

만약 쉽게 문제를 해결할 수 있다면, 주어진 답이 맞는지 검산하는 것도 쉬워요.

따라서 P는 NP의 부분집합이에요. 다시 말하면, 모든 NP 문제가 P문제인지를 살펴보면 되겠죠?

먼저 P 문제와 NP 문제의 예시를 들어볼게요. P 문제는 말 그대로 쉽게 풀 수 있는 문제예요.

“A는 B의 배수인가?” 정말 쉽죠. A를 B로 나눠보면 되니까요.

다음은 NP문제예요. 아주 큰 자연수를 두 수의 곱으로 나타낼 수 있나요? 이 수가 어떤 수든 말이에요.

거의 불가능에 가깝죠. 2나 5의 배수면 모를까, 큰 두 소수의 곱이면 알아내기도 힘들 거예요.

하지만 두 수가 주어졌을 때 그 수를 알아내는 것은 정말 간단해요. 곱해보면 되죠.

이제 P와 NP가 같다고 가정해봅시다. 모든 NP 문제는 사실 P 문제였던 거죠.

그 말인 즉슨, 어떤 문제를 쉽게 검산할 수 있다면, 그 문제를 쉽게 풀 수 있어야 해요.

큰 두 소수의 곱으로 나타낼 수 있는 다른 방법이 있었던 거죠!

그렇다면 지금까지의 수학자들은 왜 찾지 못했을까요? 이런 여러가지 이유로 많은 수학자들은 P ≠ NP라고 믿어요.

또, 본질적으로 증명은 검증보다 어렵기 때문에, NP는 P와 같을 수 없다고 믿는대요. 혹은 증명이 불가능할 수도 있겠죠.

이 문제는 1971년, 스티븐 쿡에 의해 처음 제시된 후, 50년이 지난 지금도 해결되지 않았어요.

수학의 7대 밀레니엄 난제 중 하나죠. 만약 이 문제가 증명된다면 수학을 비롯한 다양한 분야에 깊은 영향을 끼칠 것으로 예상돼요. 부와 명예는 덤이고요.

세상에는 어려운 문제도 있고 쉬운 문제도 있어요. 사람들은 쉬운 문제를 추구해요. 그리고 어려운 문제를 꺼려하죠. 그런데 만약 P-NP가 참으로 증명된다면, 어려운 문제에 더 흥미가 생기지 않을까요? 쉽게 해결하는 방법도 나올테니까요.

저도 모든 어려운 문제를 쉬운 문제로 바꿀 수 있다는 확신은 없어요. 하지만 이것 하나만큼은 확신해요.

세상에 정답은 없다는 거. 어떻게 살아갈지는 본인에게 달렸죠. 각자 좋아하는 길을 걸어가며 모두가 행복하길 바랄게요!