P=NP 문제

P : 결정론적 튜링머신 (같은 input에 대해 항상 같은 output)이 다항시간 안에 풀 수 있는 문제 - 다항 시간 알고리즘이 알려져 있다. 즉, 쉽다!

 

NP : 비결정론적 튜링머신 (같은 input이라도, 다른 output 나오기 가능; random이라고 생각)이 다항시간 안에 풀 수 있는 문제

 

명확히 알려진 다항시간 풀이는 없지만 (다항 시간이 아닌 풀이는 있을 수 있음),

랜덤하게 찍어맞추는 식으로 어떻게든 다항시간 내에 풀 수 있으면 NP.

 

+) 나 같은 빡대가리를 위해 다르게 표현한 정의가 있다!

어떤 test-case가 힌트로 주어졌을 때, 이걸로 문제가 틀린지 맞는지 다항시간 내에 검산할 수 있는 문제

→ 두 표현은 같다.

랜덤하게 우연히 한 가지 경우의 수를 트라이 해보다가, 문제를 풀어버렸을 때

= 문제를 풀 수 있는 Test-case가 주어졌을 때 문제가 풀리는지 확인

이래도 이해 잘 안가는데, 무나위키 예시 보기

 

* P문제는 NP문제에 속한다.

문제를 다항 시간 내에 풀 수 있다면, 당연히 검산도 다항 시간 내에 가능하니까.

 

P⊂NP

 

 

그래서, P=NP인가? 가 문제의 핵심이다.

만약 P=NP라면, 답이 없는 것 같아 보이던 모든 NP문제들은 사실 답이 있고, 단지 우리가 아직 찾지 못했다는 것을 의미한다 (논문 주제가 쏟아진다!)

 

하지만, 느낌상 P != NP 일 것 같다는게 학계의 추측이다.

다항시간 풀이가 알려지지않는 어려운 문제들이 사실은 풀이가 있는데, 우리가 아직 찾지 못한 것 뿐? 

 

아래 글에서 굉장히 아름답게 설명하고 있다. 꼭 읽어보자.

https://ratsgo.github.io/data%20structure&algorithm/2017/11/30/NP/

P, NP 문제 (1) · ratsgo's blog

---

여기서 더 나아가면)

 

문제 B를 A로 환원

= A를 풀 수 있다면 B도 풀 수 있는 것.

= A가 B보다 어렵다

문제 A: 주어진 n개의 숫자를 크기 순서로 정렬하는 문제
문제 B: 주어진 n개 숫자의 중간값을 계산하는 문제

 

모든 NP문제들은 '겁나 어려운 문제'로 환원될 수 있다.

이 겁나 어려운 문제를 NP-Hard라고 한다

 

NP-Hard는 NP문제가 아닐수도 있다!

근데, NP-Hard면서 NP문제인 문제들을 우리는 NP-Complete라고 한다.

 

NP-Complete는 다른 모든 NP 문제들보다 어렵다.

즉, NP-Complete 문제 하나만 다항시간 내에 풀어버릴 수 있다면, 이 세상에 존재하는 모든 NP문제들을 다항시간 내에 풀어버릴 수 있다. P=NP가 되는 것이다.

 

 

이걸 왜 알아야 하지? 같은 느낌이 들 수 있는데,

알고리즘 문제 풀 때도, 어렵고 명확한 풀이가 안보이는 이 문제가 만약 NP문제라면,

다항시간 풀이를 찾으려고 애쓸 필요 없이 깔끔하게 비-다항시간 풀이 찾고 멈추거나,

좀 더 익숙한 다른 NP-Complete 문제로 환원시킨후 해당 풀이를 활용할 수 있기 때문이다.

 

 

정지 문제 -> 못품

꺼무위키 영상 보기

https://namu.wiki/w/%EC%A0%95%EC%A7%80%20%EB%AC%B8%EC%A0%9C

 

오일러 서킷/트레일 (한붓그리기) = P

해밀턴 서킷/경로 = NP - Complete

Traveling salesman problem (TSP) - NP Hard

이산구조 시간에 배웠던가? 생각날 듯 말 듯

 

 

추가로 볼만한 Reference

★TSP Decision 문제가 NP-Complete임을 Hamiltonian을 이용해서 증명 (쉽게 잘 설명해놓음)

https://zeddios.tistory.com/176

NP-Hard, NP-Complete.mhtml

0.73MB

P와 NP의 개념.mhtml

0.51MB

TSP는 NP-Complete..mhtml

1.08MB

 

https://wkdtjsgur100.github.io/P-NP/

P, NP문제와 co-NP, NP-난해(NP-Hard), NP-완전(NP-complete) 개념 정리