2020. 7. 23에 쓴 글.
배경
컴퓨터는 문제를 자동으로 푸는 기계다.
컴퓨터(튜링 기계)는 풀 수 있는 문제에 대해 해당 문제에 대한 해법(알고리즘)만 주어진다면 그 해법에 맞게 자동으로 움직여서 답을 찾아낸다.
컴퓨터로 못푸는 문제도 존재한다( ex. Halting Problem)
그런데 사람들은 컴퓨터가 풀 수 있는 문제 중에서도 적은 비용으로 풀리는 해법(알고리즘)을 찾지 못한 문제에 대해서,
적은(현실적인) 비용으로 풀 수 있는 알고리즘이 존재하는데 아직 찾지 못한것인가? 아니면 이 문제가 너무 어려워서 현실적인 비용으로 풀 수 있는 알고리즘 자체가 없는 것인가? 하는 의문을 가졌다.
그래서 사람들은 어떤 문제가 어렵고 어떤 문제가 쉬운지 정의하려고 하게 되었다.
정의
우선 P와 NP는 기본적으로 결정문제의 집합이다.
결정문제(Decision problem)란, 결과가 True or False로 나타나는 문제를 말한다.
P class
P class의 P는 Polynomial Time을 뜻한다.
복잡하지 않고 적은 비용으로 풀리는 해법(알고리즘)이 있는 문제의 집합을 P Class 라고 할 수도 있겠지만, P class의 정확한 정의는 다음과 같다.
튜링 기계 (Turing Machine)에서 Polynomial Time Algorithm이 존재하는 Decision problem의 집합
튜링 기계란?
앨런 튜링이 1936년에 계산 가능한 수와 결정성 문제에의 응용이라는 논문에서 소개한 기계로, 초기 컴퓨터의 모델이 된다.
여기서 말하는 튜링 기계는 결정론적 튜링기계로, 한 순간에 한 가지 상태만을 가지는 튜링기계이다.
P class 문제
앞서 말한대로 튜링 기계로 Polynomial time algorithm이 발견된 문제 만을 P class 문제라고 말할 수 있는데, 어떤 문제들은 아직 P class인지 아닌지 모른다.
즉, 그 문제에 대한 Polynomial time algorithm을 아직 못 찾았는데 Polynomial time algorithm이 있는데 못 찾은건지 아니면 아에 없는지도 모르는 상태인것이다.
NP class
NP class의 NP는 non-deterministic polynomial time을 뜻한다.
No-polynomial 이 아님에 주의하자!
NP class의 정확한 정의는 다음과 같다.
비결정론적 튜링 기계(NTM)로 다항 시간 안에 풀 수 있는 Decision problem의 집합
비 결정론적 튜링기계 란?
비결정론적 튜링 기계(NTM : Non-deterministic Turing Machine)는 원래 우리가 아는 튜링기계와는 다른 작동표를 가진다.
원래 우리가 아는 튜링기계(결정론적 튜링기계)는 한 가지 상태(현재 튜링기계의 상태와 현재 읽고 있는 입력값)에서 한 가지의 Action을 가진다. 하지만 비결정론적 튜링 기계(NTM)의 작동표는 한 가지 상태에서 여러개의 Action을 가진다 (마치 다중우주론 같은 느낌).
이 개념을 잘 생각해서 NTM의 동작을 상상해보면, NTM이 계속 진행될때 튜링기계가 한 순간에 동시에 가지는 상태가 Exponential하게 증가되는 그림이 그려질 것이다.
NP class의 정의 따르면 당연히 NP class는 P class를 포함한다. (Deterministic Turing Machine의 모든 동작이 NTM으로도 가능하기 때문)
NP class의 쉬운 정의
위에서 설명한 NP class는 NPM이 어쩌고... 하는 너무 어려운 정의였다. NP class를 쉽게 정의하기 위한 말이 책(컴퓨터 과학이 여는 세계)에 나와 있다.
-
운이 좋으면 Polynomial time에 풀리는 문제.
-
답이 주어지면 그 답이 맞는지 Polynomial time 만에 확인할 수 있는 문제.
그런데 이 문장들로도 NP class가 설명이 되겠지만 뭔가 모호한 느낌이 남아있기 때문에 NTM을 사용한 정확한 정의를 이해하는게 좋을 것 같다.
P, NP의 문제 예시
P class 문제
- 주어진 배열에 23보다 큰 숫자가 있느냐?
- 주어진 배열에 중복된 값이 존재하는가?
NP class 문제
NP가 P를 포함하니 정확히는 NP - P 영역에 있는 문제들이다.
-
해밀턴 경로(모든 도시를 한 번씩만 방문하는 경로) 존재 유무를 찾는 문제
-
TSP(Traveling Salesman Problem). 주어진 예산으로 모든 도시들을 방문하고 돌아올 수 있는지 찾는 문제
-
주어진 부울식이 참이되게 할 수 있는지 찾는 문제
참고
-
컴퓨터과학이 여는 세계, 이광근 저
