알고리즘 - 22 NP-완비 문제

NP-완비(NP-Complete)군

- 지금까지 기술로 다항식 시간에 풀기 어렵다고 판단되면서 서로 밀접한 논리적 연결관계를 가진 문제들의 집합

-> 한 문제가 다항식 시간에 해결 가능하다면, 다른 문제의 답도 말해줄수 있는 경우 이 군에 속하는 모든 문제가 다항식 시간에 풀림

 

NP-완비임을 증명하는 것에 대한 의미

1. 어떤 최적화 문제를 햏결하는 효율적인 알고리즘을 찾을 수 있을 때

2. 이 문제의 yes/no 버전의 문제가 np-완비 임이 증면되면 이 문제군의 단 한문제에 대해서도 효율적인 알고리즘을 발견하지 못했음을 알 수 있음

 

 

NP-완비 이론의 상황을 비유적 예시

상사가 아주 어려운 문제를 해결하라고 지시

- 문제가 어렵다는 것을 상사에게 설득하는 세 가지 방법

1. 나는 답을 구할 수가 없습니다. 아마 나는 멍청한 모양입니다.

2. 나는 답을 구할 수가 없습니다. 왜냐하면 이 문제는 답이 없어요.

3. 나는 답을 구할 수가 없습니다. 그렇지만 저렇게 수많은 천재들도 이 문제를 해결할 수 없습니다

 -> NP-완비 이론의 상황을 비유적으로 보여줌

=> 상사가 준 문제를 NP 완비임을 안다면 수많은 천재들도 풀지못한 어려운 문제에 속함을 알 수 있음

 

NP-완비의 정의

- 문제 A가 다음의 두 조건을 만족하면 NP-완비임

-> A는 NP이다

-> A는 NP-Hard 이다.

 

NP-하드의 정의

- 문제 A가 다음 성질을 만족하면 NP-하드임

-> 알려진 임의의 NP-하드 문제 L로부터 문제 A로 다항식 시간에 변환 가능하다.

-> 모든 NP 문제가 L에 대해 L <=_p A이다.

=> 만일 문제 A를 쉽게 풀수 있다면, 문제 L도 쉽게 풀 수 있음 => 그러므로 모든 NP 문제를 쉽게 풀 수 있음

문제 A를 푸는 알고리즘

 

NP-완비 문제들