문제의 종류
모든 문제들은 풀 수 있는 문제와 풀 수 없는 문제로 나뉜다.
이때, 풀 수 있는 문제들을 어떻게 분류할 수 있을까?
여기서 가장 중요한 것은 "현실적인 시간안에 풀 수 있는가?" 이다.
아무리 풀 수 있을 것 같아도 현실적인 시간 안에 풀 수 없으면 아무 소용이 없기 때문이다.
이때 여기서 현실적인 시간안에 풀 수 없다는 것이 증명된 문제들을 다루기 힘든 문제라고 한다. 이와는 반대로 현실적인 시간안에 풀 수 있다는 것이 증명된 문제들은 P라고 한다.
그렇다면 이 풀 수 있는 문제들은 다루기 힘든 문제와 P에 속한 문제들만 존재할까? 이것도 아니다. 이 세상에는 아직 이 둘중에 어디에 속해있는지 모르는 문제들이 많이 존재한다. 즉 다루기 쉽다고 증명되지 않았지만 그렇다고 다루기 힘들다고 증명된 것도 아닌 문제들이다.
이러한 문제들이 NP문제이다.
1. P
1) 정의
Polynomial Time에 해결할 수 있는 문제들을 의미한다.
즉,
O(1),O(log n),O(n log n),O(n^2), ...과 같은 Time Complexity를 갖는 문제들을 의미한다.
2) 예시
- 정렬:
O(n log n)- 탐색:
O(log n)- 행렬곱셈:
O(n^2.38)- 최소 비용 신장 트리
- 연쇄행렬곱셈
- 최단경로
- ...
2. NP
1) 정의
Non-Deterministic Polynomial Time인 문제들을 의미한다.
이 문제들은 답을 알아맞추기 위해 추측(Non-Deterministic)이 필요하고
해당 답을 검증하는 것은 Polynomial Time에 수행할 수 있는 알고리즘을 의미한다.(주의: Polynomial Time인지 정해지지 않았다는 뜻이 아니다.)
(이런 문제들은 답이 될 수 있는 모든 n에 대해 확인하는 것이 좋을 수도 있다?)
이 때, P=NP인지 P가 NP에 속하는지는 아직 아무도 모른다.
2) 예시
- KnapSack Problem
- 외판원 문제(TSP)
- 해밀토니안 회로문제
3) NP vs NP-Hard
NP Complete
: 정해진 NP문제들 중 한 문제만 Polynomial Time에 풀리더라도 모두 풀릴 수 있도록 증명된 NP 문제들.
(1st NP-Complete문제는 GSAT 문제이다. 이 문제를 풀 수 있으면 풀리는 문제들이, 결국엔 다시 이 문제를 풀 게 만들 수 있어 그 문제들 중 하나만 풀리더라도 전부 풀 수 있게 된다.)
NP Hard
: NP는 결정문제만 다루었었다. 이 때, NP Hard는 이 결정문제들을 최적화 문제로 확장한 문제들을 의미한다.
즉, 다항시간 안에 확인하는 것도 불가능한 문제를 말한다.
최적화 문제와 결정 문제
최적화 문제란 다항시간 안에 확인이 불가능한 문제들을 의미한다.
예를들어 TSP문제에서 주어진 경로가 최적의 경로인지 확인하는 문제가 있다.
(이 경우에는 원래 TSP문제와 달라질 것이 없다.)반면에 결정문제는 추측한 답이 맞는지를 다항시간 안에 확인이 가능하다.
예를들어 주어진 그래프에서 여행 경로가 15보다 크지 않은 경로를 찾는문제가 있다.
