P-NP 에 대하여

개요

 

밀레니엄 문제 ( http://bit.ly/2XpL3tq ) - 수학의 7대 난제중 하나에 P-NP 문제가 있다.

P-NP 에 대하여 정리를 해보고 싶어졌다.

 

참고 링크들

 

나무위키: http://bit.ly/2XgvJiR

유튜브: 수학의 신 동영상 https://youtu.be/nxbufH4JnpA - 기본적인 쉬운 이해에 도움

추가 유튜브 https://youtu.be/u2DLlNQiPB4  https://youtu.be/YX40hbAHx3s

블로그

- https://zeddios.tistory.com/92

- https://zeddios.tistory.com/93

- https://zeddios.tistory.com/176

 

P vs NP problem

 

(처음 보는 분은 무슨 말인지 모르겠지만)

현재로서는 P 가 NP 의 부분 집합이지만, 알고보면 P = NP 인지를 증명하려는 것이다.

 

한 줄로 풀어서 말하자면, "쉽게 검산할 수 있는 모든 문제는 쉽게 풀리는가?" 이다.

- P 문제는 풀기도 쉽고, 검산 (verify)도 쉬운 것이고, - NP 문제는 풀기는 어렵지만, 검산은 쉬운 것인데, - 실제로는 NP 문제들이 풀기도 쉬운 것인지를 증명하는 것이다.

 

셋 중 하나의 결론을 증명해내면 문제를 푼 것이다.

1) P = NP 이다. 2) P != NP 이다. 3) 증명하는 것은 불가능하다.

→ 다만 증명을 못할 뿐이지 대부분 학자들은 P != NP 일 것이라 예측하고 있다.

 

문제를 얼마나 빨리 풀 수 있는가?

 

문제를 빨리 푼다는 것은 컴퓨터로 치면  몇 번의 명령 수행이 필요한지로 볼 수 있다.

이때 명령 수행 개수는 컴퓨터의 클럭에 좌우되므로 결국 시간과 비례한다.

 

Polynomial time

 

다항식의 다항이란 변수가 몇 개인가를 보여준다.

x + 2y = 0 은 x, y 의 변수가 있으니 이항식이다. x + 3y2 + 6z = 5 는 x, y, z 의 변수가 있으니 삼항식이다.

 

차수란 변수에 붙은 가장 큰 승수를 보면 된다.

x + 3y2 + 6z = 5 는 삼항 이차식이 된다. 단, x + 3xy2 + 6z = 5 라면 삼항 삼차식이 되는 것에 주의 할 것. xy2 = 3차식

 

다항 시간 (Polionmial time) 에 문제를 풀 수 있다는 것은 어느 정도 감당할 수 있는 시간이라는 것이다.

철수야 도서관 책을 작가 순서대로 정리해줄래? 얼마나 걸릴까? 다항식 시간에 가능해!

* 다항 시간이면 써먹을 수 있다고 하지만, 알고리즘이 실제적으로 쓸만하려면 대략 3차식 이하여야 한다고 생각하면 편하다.

 

Exponential time

 

지수 시간이라면 망했다고 생각하면 된다.

 

다항 시간이라면 입력값의 k 차수만큼의 시간이 걸린다면 지수 시간이라면 k 상수의 입력값 차수만큼의 시간이 걸린다는 것이다.

 

P 와 NP 의 정의

 

P: set of decision problems solvable in polynomial time by a deterministic Turing machine. 

NP: set of decision problems solvable in polynomial time by a non-deterministic Turing machine 

 

둘 다 다항 시간 (polynomial time) 에 풀 수 있는 문제인데, 사용하는 기계가 deterministic 이냐 non-deterministic 이냐의 차이 이다.

deterministic 은 일반적인 우리 컴퓨터라고 보면 되고, non-deterministic 는 현실에서는 불가능하다고 보면 된다.

 

non-deterministic Turing machine

- 엄청 운이 좋은 컴터이거나 - 모든 경우의 수를 동시에 계산할 수 있는 녀석이다.

 

아래 그림을 보자 (정확히 맞는 그림은 아니지만 찰떡같이 이해해 주시길)

 

1) 만약 deterministic 이라면 모든 경우의 수를 다 따져봐야 한다.  그러면 다항 시간이 아닌 지수 시간이 걸리게 된다.

2) 만약 non-deterministic 이라면

- 매우 운이 좋은 녀석이라 딱 적절한 경우를 기가 막히게 찾아내면 다항 시간에 풀 수 있다.

- 모든 경우의 수를 동시에 계산할 수 있으면 역시나 다항 시간에 풀 수 있다.

→ 그런데 현실에서는 non-deterministic Turing machine 은 없다!

 

 

< 출처: https://skymind.ai/wiki/decision-tree >

 

P 와 NP 의 예시

 

P 의 예	NP 의 예
- 더하고 곱하는 문제 - 정렬 문제	- 더해서 0이 되는 부분 집합 찾기 - traveling salesman problem

 

NP 와 Heuristic (통밥)

 

문제: 부분 집합의 합이 0 인 경우를 하나 찾아보시오 전체 집합 A = { 4, 7, 2, - 11, 8, -3 }

 

프로그램을 짠다면 모든 부분 집합을 다 뽑아 내야 하고 그것은 지수 시간이 걸릴 것이며,

이후 그 부분 집합들의 합을 다항시간에 계산하여 0인지를 확인해야 할 것이다.

 

하지만 잉간 이라면?

딱 보니깐 부분 집합 {4, 7, -11} 은 합이 0이다. 이런 걸 통밥 (heuristic) 이라고 한다.

그리고 많은 NP 문제는 어느 정도 통밥으로 다항 시간에 해결 된다.

 

흥미로웠던 부분이며, 인간의 통밥이 어떤 프로세스로 이루어지는지를 파헤치고,

그 통밥을 좀더 고도화한 알고리즘을 만들어 볼 수 있지 않을까 싶었다.

 

 

풀기도 쉽고 검산도 쉬운가?

 

P 문제는 풀기도 쉽고, 검산도 쉽다.

NP 문제는 답을 알고 있으면 맞는지는 알기 쉬운데, 풀기는 어렵다.

대부분의 암호체계는 이처럼 풀기는 어렵지만, 답을 알고 있다면 검산은 쉽다.

 

여기에서 위에 언급한  "쉽게 검산할 수 있는 모든 문제는 쉽게 풀리는가?" 라는 질문이 나오는 것이며

- 이 질문이 바로 P 는 NP 인가 하는 질문이 되는 것이다.

 

NP-Hard 와 NP-Complete

 

< 이미지 출처: https://www.wikiwand.com/en/NP_(complexity) >

 

NP-Hard

 

여기에는 환원 (reduction) 이라는 표현이 나오게 된다.

 

1) 입력된 모든 정수를 정렬하시오 2) 입력된 모든 정수 중에서 가장 큰 값은? 3) 입력된 모든 정수 중에서 가장 작은 값은?   2) 3) 은 1) 만 해결되면 어렵지 않은 문제들이다. 2) 3) 문제는 1) 로 환원 (reduction) 할 수 있다고 표현할 수 있겠다.

 

NP 문제들은 특정한 NP 문제만 해결된다면

모두 그 NP 문제로 환원 (reduction) 하여  다항 시간에 문제를 풀 수 있다.

→ 그 특정한 NP 문제들이 NP-Hard 이다.

 

NP-Complete

 

NP-Hard 이면서 NP 인 문제를 NP-Complete 라고 한다.

이 놈이 해결된다면 다른 NP 들이 모두 이놈으로 환원되어 다항 시간에 해결된다는 것이다.

이 놈들은 NP 이지만 P 일 가능성이 열려있는 놈들이다.

 

하지만 절대로 P 일 수 없는 NP-Hard 문제도 있다.

다시말해 NP-Hard 이면서 NP 가 확실히 아닌 (=NP-Complete 가 아닌) 문제이다.

즉, 죽었다 깨어나도 다항 시간에 풀릴 수 없다는 것이 증명된 문제들이며 대표적인 것이 정지 문제 이다.

 

P = NP 라면 어떻게 되는데?

 

누구든 다항 시간안에 풀리는 공식대로만 하면

- 하바드 대학교 가고

- 영화 기생충 같은 것도 찍을 수 있고

- 모짜르트 음악도 하루에 10개 작곡 하고

- 암호도 한방에 풀 수 있다.