P, NP, NP hard 문제란

안녕하세요. 이번에는 P, NP, NP hard 문제가 무엇인지 정리해보려고 합니다.

제가 많이 공부했던 MAPF 문제가 NP hard인데 정작 NP hard 문제가 무엇인지는 모르고 있더라고요.

다항 시간에 풀리지 않는 문제가 NP 문제이고, NP hard는 NP보다 어려운 문제였니...?

이번 기회에 정리해보겠습니다.

---

1. P 문제가 무엇일까요?

P 문제는 결정론적 튜링머신으로 다항 시간 안에 해결할 수 있는 문제입니다.

복잡도로 표현하면 입력 크기 n에 대해서 문제 해결에 걸리는 시간이 O(n^k)와 같이 다항식으로 표현되는 문제들을 의미합니다.

정렬 문제, 경로 계획 문제(SAPF) 등이 있습니다.

2. NP 문제는 무엇일까요?

일단 다항 시간에 풀리지 않는 문제라는 정의는 틀렸습니다.

 

NP 문제의 올바른 정의는 비결정론적 튜링머신으로 다항 시간 안에 해결할 수 있는 문제입니다.

• 다른 표현으로는 주어진 답이 올바른 해인지 검증하는데 다항 시간이 걸리는 문제라고도 합니다.

결정론적 튜링머신으로 다항 시간 안에 해결할 수 있는 P 문제들은 모두 NP 문제인 것입니다.

 

우리가 흔히 어렵다고 말하는 NP 문제들은 사실 NP complete, NP hard 문제들입니다.

 

3. NP complete, NP hard 문제는 무엇일까요?

모든 NP 문제들이 다항 시간 내에 변환될 수 있는 문제를 NP hard 문제라고 합니다.

 

NP hard 문제면서 NP 문제면 NP complete 문제라고 합니다.

대표적인 NP complete 문제로 충족 가능성(SAT) 문제가 있습니다.

• 모든 NP 문제들을 어떻게 SAT 문제로 변환할 수 있는지 궁금하시다면 쿡-레빈 정리 를 참고하세요!

 

+++ 결정론적, 비결정론적 튜링머신이 뭐에요?

간단하게 설명하면 한번에 하나의 문제를 풀 수 있는 것이 결정론적 튜링머신이고, 동시에 여러 문제(한계가 없음)를 풀 수 있는 것이 비결정론적 튜링머신입니다.

 

비결정론적 튜링머신은 이론적인 분석을 위한 개념으로 현실 세계에는 존재하지 않습니다.