[개인 공부] 계산 복잡도 클래스: P, NP, NP-완비

안녕하세요 HoonIOS입니다 :)

이번에는 저번 시간에 이어서 P문제와 NP 문제, NP-난해 문제에 대해 알아보겠습니다.

P문제란?

우리가 정의하는 문제의 어려움은 우리가 문제를 풀 때의 난이도가 아니라 계산 복잡도 이론에서 문제의 난이도는 해당 문제를 해결하는 빠른 알고리즘이 있느냐를 나타내는 것입니다.

 

여기서 빠른 알고리즘이 있는 문제는 계산적으로 쉽고, 빠른 알고리즘이 없는 문제는 계산적으로 어렵다고 합니다.

이 말은 즉 알고리즘을 유도하는 과정이 책이 열 권이고 그 구현이 아무리 길어도 수행 시간만 빠르다면 이건 쉬운 문제가 된다는 것을 알 수 있습니다.

 

그럼 여기서 빠른 알고리즘의 기준이 뭐라고 할 수 있을까요?, 그 기준은 우리는 다항시간 알고리즘이나 그보다 빠른 알고리즘만을 빠르다고 할수 있습니다.

 

계산 복잡도 이론에서 이렇게 다항 시간 알고리즘들이 존재하는 문제를 P문제라고 부릅니다.

 

P문제처럼 같은 성질을 갖는 문제들을 모아놓은 집합을 계산 복잡도 클래스라고 부른다고 할 수 있습니다.

 

* 난이도의 함정

- 계산 복잡도에서 흔히 말하는 어려운 문제는 다음과 같습니다.

• 정말 어려운 문제를 하나 잘 골라서 이것을 어려운 문제의 기준으로 삼고 이 기준 문제만큼 어렵거나 그보다 어려운 문제를 어렵다고 부릅니다.
  
  
• 그러나 위 어려운 문제를 판별하는 것은 쉽지 않습니다.
  예를 들어 문제 A가 문제 B이상으로 어렵다고 말하면 A는 가장 빠른 알고리즘이 B를 푸는 가장 빠른 알고리즘 이상의 시간이 걸려야 하는데 대부분은 우리가 푼 문제가 가장 빠른 지를 모른다....ㅎㅎㅎ( 알면은 알고리즘이 어렵다는 말은 안 하겠죠...?ㅠ) 또 우리가 지금 푼 문제가 가장 빠른 알고리즘 인지도 모릅니다.

- 이를 해결하기 위해 계산 복잡도 이론에서는 두 문제의 난이도를 비교하기 위해 환산이라는 기법을 활용합니다.

* 환산이란?
- 한 문제를 다른 문제로 바꿔서 푸는 기법입니다.

- 예를 들어, B의 입력을 적절히 변해 A의 입력으로 바꾸는 환산 알고리즘이 존재한다고 하면 이때 A를 푸는 가장 빠른 알고리즘을 가져와 이것을 환산 알고리즘과 결합해 B를 푸는 알고리즘으로 만들수 있습니다.

- 만약 환산 알고리즘이 무시할수 있을정도로 빠르다고 가정을 하면 이것과 결합된 알고리즘 A를 푸는 가장 빠른 알고리즘과 같은 시간이 거릴것입니다. B를 푸는 가장 빠른 알고리즘은 A를 푸는 가장 빠른 알고리즘과 같거나 더 빠를수 밖에 없습니다.

NP 문제, NP- 난해 문제란?

- 이제 어려운 문제의 기준을 정해 보면 어려운 문제의 기준이 되는 것은 바로 SAT(Satisfiablility Problem)입니다.

 

*SAT 문제란?

• N개의 불린 값 변수로 구성된 논리식을 참으로 만드는 변수 값들의 조합을 찾는 문제입니다.
• 예를 들어 설명해보면 값 변수 a, b, c로 구성된 다음 논리식은 세 변수의 값이 특정 조합을 이루어야 만족이 됩니다.(a||b||! c) && (! c||! a) && (! a && b) || (b &&! c) && (! b || (! a &&! c))

- SAT 문제는 아주 중요한 의미가 있습니다. 바로 SAT문제는 모든 NP 문제 이상으로 어렵다는 것입니다.

- 이제 NP 문제의 정의에 대해 알아보겠습니다.

• NP 문제란 답이 주어졌을 때 이것이 정답인지를 다항 시간 내에 확인할 수 있는 문제를 의미한다.
• 예를 들어, 부분집합 합 NP 문제가 있습니다. 부분집합 합 문제의 답이 주어졌을 때 이것이 원래 집합의 부분집합인지 그리고 원소들의 합이 S인지 다항 시간에 쉽게 확인할 수 있기 때문입니다.

- 모든 P문제들은 NP 문제에 포함이 되어있습니다.

- SAT가 모든 NP문제 이상으로 어렵다는 말은 SAT를 다항 시간 안에 풀 수 있으면 NP 문제들은 전부 다항 시간에 풀 수 있다는 이야기가 됩니다.

- 이런 속성의 문제들을 가지는 문제들의 집합을 NP-난해 문제라고 부릅니다.

- NP-난해 문제이면서 NP인 문제들을 NP-완비 문제라고 합니다.

P=NP란?

- P=NP 문제는 P와 NP가 같은지를 확인하는 문제입니다.

- NP-난해 문제 중 하나를 다항 시간 안에 풀 수 있다면, 이 알고리즘을 이용해 NP에 속한 모든 문제를 다항 시간에 풀 수 있습니다.

- 이경우 NP에 속환 모든 문제를 다항 시간에 풀수 있으므로 P=NP 임을 확인할수 있습니다.

- 반대로 만약 다항시간에 푸는 방법이 없음을 증명을 하면 P!= NP임을 볼 수 있습니다.

- 다항 시간을 해결할 수 있는 P=NP와 다항 시간으로 풀 수 없을 증명하는 P!= NP 둘 중 하나라도 증명을 성공한 사람은 없다고 합니다...ㅎㅎㅎ

 

- 문제를 이용해 NP-난해나 NP완비 문제 중 하나를 풀 수 있음을 깨달았다고 하자, 이경우에는 효율적으로 풀려고 발버둥 치는 대신 모델링을 하거나. 근삿값을 찾는 등 다른 방향으로 돌아가는 길을 모색하는 것이 합리적입니다.

 

P, NP, NP완비, P=NP에 대해 알아봤습니다 좀 어려우긴 하지만... 문제를 푸면서 무슨 형식인가에 대해 생각하면서 풀면 좋을 것 같다는 생각을 했습니다...!!