P와 NP에 대해서 알아보자
문제의 집합
P(Polynomial probelm)와 NP(Non-deterministic Polynomial probelm) 모두 결정 문제의 집합이다.
쉽게 답을 낼 수 없는 문제에 대해서 문제를 더 풀이할 가치가 있는가 없는가를 결정하기 위해 문제를 분류하고 메타적으로 이해할 필요가 있다.
쉽게 말해서 어떤 문제가 곱게 풀릴 것 같지 않을 때 각을 재보고 안되겠다 싶으면 다른 방법을 찾아야겠죠? 그 판단을 하기 위해서 필요한 것임.
- P 문제: 문제를 polynomial 시간 (다항 시간) 내에 해결할 수 있다.
- NP 문제: 어떤 입력(certificate)에 대해 해결할 수 있음을 Nondeterministic Turing machine으로 Polynomial 시간 안에 검증할 수 있다.
그림에서 certificate는 문제의 input instance의 형식을 지키는 어떤 임의의 instance다. (a는 b의 배수인가? -> input은 a,b -> certificate은 3, 7 같은 게 될 수 있다)
P와 NP의 가장 큰 차이는 문제의 답을 찾는 데 걸리는 시간에 집중 vs 문제의 답을 검증하는 데 걸리는 시간에 집중이라고 할 수가 있다.
NP의 N은 Non이 아니다
사실 문자만 보면 맞기도 한데 아무튼
NP의 정의는 다항 시간에 풀리지 않는 문제의 집합이 아니다. NP의 N은 Non-deterministic이다.
Non-deterministic (비결정적)이 뭔지 이해하려면 deterministic이 뭔지부터 이해해야 된다.
deterministic 결정적
결정적이라는 건 어떤 상황에서 어떻게 흘러갈지 결정되어 있다는 것을 말한다.
P와 NP를 정의하고 해결하는 데 사용하는 튜링 머신에서는 같은 state 같은 input symbol에 대해 하나의 동작만 정의되어 있는 것을 deterministic하다고 말한다. 튜링 머신까지 설명하기는 너무 길어지므로... 생략
Non-deterministic 비결정적
비결정적이라는 건 결정적과 반대로 어떤 상황에서 어떻게 흘러갈지 결정되어 있지 않은 것이다.
튜링 머신에서 같은 state 같은 input symbol에 대해 여러 개의 동작이 정의되어 있는 것을 Non-deterministic하다고 말한다.
그래서 NP는 뭐냐면 Non-deterministic Turing machine을 사용해서 어떤 문제에 어떤 certificate을 넣었을 때 이 certificate이 답인지 아닌지 polynomial time에 검증할 수 있는 문제인 것이다.
그러면 이제 아래 두 명제가 참인지 거짓인지 생각해볼 수 있다.
정의에 대한 두 가지 명제
- P에 속하는 모든 문제는 NP에 속한다.
- 옳다고 증명되어 있다.
- 왜냐면 polynomial time에 답을 찾을 수 있는 문제이므로, 어떤 certificate이 주어졌을 때 이것으로 문제를 해결할 수 있는지 없는지도 polynomial time에 찾을 수 있다.
- Deterministic TM에 의해 polynomial 시간에 해결되는 모든 문제는 Nondeterministic TM에 의해 polynomial 시간에 해결할 수 있다.
- 이것도 옳다
- 왜냐면 NTM은 한 번에 하나의 경로만 테스트하는 게 아니라 트리 형태가 되어 병렬적으로 경로를 탐색하기 때문이다. 여러 branch 중에 한 곳에서 정답을 찾으면 해결한 것이다.
- DTM으로 polynomial 시간에 해결되는 경로가 존재한다면, NTM에도 polynomial 시간에 해결되는 경로를 만들 수 있다.
- 사실 이 문제 때문에 포스트 쓰기 시작함
- DTM은 경로가 결정적이고 NTM은 훨씬 많고 비결정적일 텐데 NTM이 더 오랜 시간이 걸리는 거 아닌가? 라고 생각했었는데 병렬로 동시에 풀이를 진행하기 때문에 결국 DTM으로 풀 수 있다면 NTM에서도 같은 시간에 문제를 해결할 수 있다.
시험기간에 유익한 딴짓 하는 거 되게 재밌네
