[밀레니엄 난제] P-NP문제

*저는 전문가가 아닙니다. 가볍게 이해하고 넘어가는 느낌으로 보시는 것을 추천합니다*
*틀린 부분이 있을 수 있습니다*

---

P-NP문제는 제목에서 말했듯이 밀레니엄 난제 중 하나로, 무려 11억원이 걸려 있습니다. 다른 말로 하면 그만큼 어렵다는 뜻이죠.

도대체 어떻게 생겼는지 한번 구경이나 해봅시다.

  P집합은 NP집합과 같다  

11억원짜리 치고는 간단하게 생겼네요.

---

시간복잡도

P-NP문제를 풀기 위해서는 당연히 P집합과 NP집합을 알아야 합니다. 그리고 이들을 이해하기 위해서는 '시간복잡도' 가 무엇인지 알아야 합니다.

시간복잡도란 컴퓨터가 알고리즘을 짤 때 얼마나 오랜 시간이 걸리는가를 나타내는 지표입니다. 컴퓨터과학이 나와도 수학 문제가 맞습니다

예를 들어, 1부터 10000까지 더하는 알고리즘을 짠다고 칩시다. 그렇다면 여기에는 2가지 방법이 있습니다.

1) 1+2+3+4+.......+10000을 전부 입력한다.
2) 가우스의 공식을 빌려, (10000X10001)/2 만 입력한다.

당연히 후자가 훨씬 쉽습니다. 그래서 컴퓨터과학자들은 이렇게 '빠른' 알고리즘을 찾으려고 합니다.

---

빠르기

그렇다면 빠른 알고리즘을 찾아야 하는 건 알겠는데, 도대체 '빠르다'의 기준이 뭘까요?

만약 푸는 데 n시간이 걸리는 알고리즘과, 2^n시간이 걸리는 알고리즘이 있다면 n시간 걸리는 알고리즘이 더 빠르다는 것은 자명합니다.

사실 2^n의 증가 속도는 매우 빨라서, 시간복잡도가 다항식이기만 하면 (1차든, 2차든, 3차든, 심지어 100차라도!) 2^n보다 걸리는 시간이 짧습니다. n이 커지면 커질수록 더 그렇습니다.

이처럼 컴푸터과학자들은 오랜 연구 끝에 '다항식'이 가장 계산 속도가 빠르다는 것을 알아냈습니다. 그리고 다항 시간이 소요되는 알고리즘을 '빠른 알고리즘'으로 정의했습니다.

---

P와 NP

이제 P집합과 NP집합을 정의할 차례입니다. P문제는 '빠르게', 그러니까 다항 시간 내에 풀 수 있는 문제를 뜻합니다.

그럼 NP문제는 무었일까요? NP문제란, 이미 답을 알고 있을 때 답이 맞는지 빠르게 확인할 수 있는 문제를 뜻합니다. 즉 다항 시간 내에 검산할 수 있는 문제를 말하죠.

---

P-NP문제

P-NP문제의 정의를 다시 살펴봅시다.

P집합은 NP집합과 같다.

앞서 배운 정의를 생각해보면 다음과 같이 바꿔 쓸 수 있습니다.

빠르게 검산할 수 있는 문제는 빠르게 풀 수 있고,
빠르게 풀 수 있는 문제는 빠르게 검산할 수 있다