Algorithm design - P-NP

---

P-NP problem

P-NP problem의 P는 polynomial-time algorithm의 P이고 polynomial-time algorithm은 입력의 크기가 n일 때, 최악의 경우 수행시간이 W(n)∈O(p(n))인 알고리즘을 뜻한다. 여기서 p(n)은 n의 다항 함수이다. 예를 들어 아래와 같은 알고리즘들이 존재한다.

정렬문제: Θ(nlogn)
정렬된 배열 검색 문제: Θ(logn)
행렬곱셈 문제: Θ(n^2.38)

 

NP는 Nonpolynomial이 아니라 Nondeterministic Polynomial이다. 이는 nondeterministic한 guessing으로 해답을 추측하고 해당 답이 정답인지 검증하는 과정이 polynomial하다는 것이다.

변환(reduction)을 통해 알고 있는 문제와 연관지어 다른 문제를 정의할 수 있다. 예를 들어 문제B는 이미 푸는 방법을 알고 있을 때 문제 A는 Yes/No 대답이 일치하는 문제 B로 쉽게 변형이 된다.

문제A의 사례α를 문제B의 사례β로 바꾸되 아래 성질을 만족하면 polynomial-time reduction이라 한다.
1. 변환은 다항식 시간에 이루어진다.

2. 두 사례의 답은 일치한다.

어떤 결정 문제에 대해서 검증을 다항 시간에 하는 알고리즘이 있다면, 그 결정 문제는 NP에 속하기 때문에 아래와 같은 관계가 성립한다.

지금까지는 왼쪽처럼 P는 단순히 NP에 포함되는 관계일거라고 예상되고 있지만 만약 P=NP라는 것이 밝혀진다면 모든 NP문제를 P문제로 해석할수 있기에 세계 수학 7대 난제에 포함되어있다.

---

NP-complete

Cook이 최초로 NP-complete을 정의하였다.

Cook의 정리
문제 B는 다음 두 조건을 만족하면 NP-complete이다.
(1) 문제 B가 NP에 속하고,
(2) 잘 알려진 NP-complete문제 A에 대하여 A≤pB이면 B는 NP-complete이다.

다시 말해서 NP-complete은 NP문제의 대표자들 이라고 보면 된다. 이중 하나라도 P로 해결한다면 reduction을 통해 모든 문제를 해결해낼 수 있다. N=NP problem을 풀어내는 것이다.

---

NP-hard

결정문제에서 최적화문제로 확장한 것이 NP-hard이다.
정의: 문제B를 푸는 가상적인 다항시간 알고리즘을 사용하여 문제A를 다항시간에 풀 수 있다면, 문제A는 문제 B로 다항시간 튜링 축소가능(polynomial-time Turing reducible)하다라고 한다.
임의의 NP-complete문제 A에 대해서 위 관계가 성립하면 문제 B는 NP-hard 하다고 한다.
NP-complete에 상응하는 최적화 문제는 모두 NP-hard이다. 예를들어 TSP decision problem로부터 TSP optimization problem이 NP-hard problem임을 알 수 있다.

모든 NP-complete은 NP-hard문제이다.
다만 NP-hard에 속하지 않는 문제는 무엇인지 아직 모른다. 어떤 문제가 NP-hard가 아니라고 증명하게 된다면 P ≠ NP임을 증명하게 되는 것이다. 다항시간 알고리즘을 발견한 문제는 NP-hard가 아닐지도 모르지만 만약 다항시간 알고리즘이 있는 어떤 문제가 NP-hard임을 증명하면 P=NP임을 증명하게 되는 것이다.

---