14-2 NP 완전 문제

1. 문제의 종류

① 문제의 종류

 - 풀 수 있는 문제와 풀 수 없는 문제로 나뉨.

 - 현실적인 시간안에 풀 수 없는 문제는 근사해를 구하는 것을 목표로 할 수 밖에 없음

 - NP 완전 문제

   : 현실적인 시간에 풀 수 없다 추정되면서 서로 강력한 연관성을 가진 특이한 문제군에 관한 것.

 

② 현실적인 시간

 - 다항식 시간을 의미 (= 현실적인 시간)

   > 문제의 크기가 n이면 그 문제를 푸는데 n의 다항식에 비례하는 시간이 드는 알고리즘

   > 어떤 문제가 다항식 시간에 해결되면 현실적인 시간에 풀 수 있다고 간주

 - 비현실적인 시간

   > 문제를 해결하는데 비다항식의 시간이 소요되면 현실적인 시간에 풀 수없는 경우로 간주 (지수시간, 계승시간)

 

2. YES/NO 문제와 최적화 문제

① YES/NO 문제 - 결정문제

  - ex) 그래프 G에서 길이가 k이하인 해밀턴 경로가 존재하는가?

② 최적화 문제

  - ex) 그래프 G에서 길이가 가장 짧은 해밀턴 경로는 얼마인가?

3. NP 완전문제

① P(polynomial)

  - 다항식 시간에 해결할 수 있는 문제들의 군

  - 결정문제들 중에서 쉽게 풀리는 것을 모아 놓은 집합

  -  다항식 시간 내에서 더 적은 시간을 소요하는 알고리즘을 개발하는데 초점 맞춰짐

  - 컴퓨터 같은 계산 장치를 이용해 합리적인 시간 내에 풀 수 있는 형태의 문

 

② NP (Nondeterministic Polynomial) : 비결정적 다항식 문제

 - 결정 문제들 중에서 적어도 검산은 쉽게 할 수 있는 것 모아 놓은 집합

 - 결정 문제의 답이 Yes일 때, 그 문제의 답이 Yes라는 것을 입증하는 힌트가 주어지면 그 힌트를 사용해서 

    그 문제의 답이 정말 YES라는 것을 다항식 시간 이내에 확인할 수 있는 문제

 - 일반적으로 모든 P문제는 NP문제임

 

③ NP  - 난해(NP hard) 문제

  - NP문제 보다 어렵고, 모든 NP문제를 다항식 시간 내에 어떤 문제로 환원할 수 있는 경우 그 문제를 NP 난해 문제라고 함

  - NP 난해 문제를 다항식 시간 내에 풀 수 있으면 모든 NP 문제를 다항식 시간 내에 풀 수 있음.

  - NP-난해 문제 중 NP 문제가 아닌 것도 있다.

 

④ NP- 난해 증명의 예

 - 해밀턴 사이클 문제가 NP 난해임을 알고 있다 가정

 -> 이를 이용해서 TSP 문제가 NP-난해임을 보일 수 있음

⑤ NP- 완전문제

  - NP - 난해에도 포함, NP-문제에도 포함되면 NP- 완전 문제라고 부름

⑥ 현재까지 연구 결과

  - 어떤 문제가 NP-완전임이 확인되면 현실적 시간안에 풀 수 있는 방법 아직 없음

  - 명제 P=NP 증명 X

⑦ 다항식 시간 변환

⑧ NP 이론의 유용성

  - 어떤 문제가 NP 완전/난해임이 확인되면 

    > 쉬운 알고리즘 찾으려는 헛된 노력 중지

    > 주어진 시간 예산 내에서 최대한 좋은 해 찾는 알고리즘 개발에 집중

⑨ P와 NP의 포함관계