[알고리즘] 7. NP-완전 문제

 

• P는 다항 시간(polynomial time)에 결정론적(deterministically)으로 해결 가능한(solvable) 문제들의 집합입니다. 다시 말해, 어떤 결정 문제(decision problem) X에 대해, 주어지는 입력(input)이 참인지 거짓인지를 다항 시간에 결정론적으로 해결하는 알고리즘이 존재하면 X∈P입니다.

 

• NP는 다항 시간에 비결정론적(nondeterministically)으로 해결 가능한 문제들의 집합으로, 어떤 결정 문제 X에 대해, 주어지는 입력이 참인지 거짓인지를 다항 시간에 비결정론적으로 해결하는 알고리즘이 존재하면 X∈NP입니다.
• NP의 또 다른 정의는 다항 시간에 결정론적으로 검증 가능한(verifiable) 문제들의 집합입니다. 자세히 살펴보자면, 어떤 결정 문제 X에 대해 어떤 입력과 입력 크기의 어떤 다항식으로 표현되는 크기를 갖는 증거(certificate)를 함께 제공 받았을 때 이를 다항 시간에 결정론적으로 검증하는 알고리즘이 존재하면 X∈NP입니다.

 

NP-완전 문제 중 하나라도 P에 속한다는 것을 증명한다면 모든 NP 문제가 P에 속하기 때문에, P-NP 문제가 P=NP의 형태로 풀리게 된다. 반대로 NP-완전 문제 중의 하나가 P에 속하지 않는다는 것이 증명된다면 P=NP에 대한 반례가 되어 P-NP 문제는 P≠NP의 형태로 풀리게 된다.

 

 

문제의 변환과 환원

문제의 변환

• 문제 A를 해결하기 위해서 문제 B를 해결하는 알고리즘을 이용하는 것

문제 변환 과정

• 문제 A의 입력을 문제 B의 입력 형태로 변환
• 변환된 입력으로 문제 B를 해결하는 알고리즘 수행
• 수행 결과인 해를 문제 A의 해로 변환
  

  

문제 변환 시간복잡도

• 문제 A의 입력을 문제 B의 입력으로 변환하는 시간
  • 다항식 시간
• 문제 B를 위한 알고리즘이 수행되는 시간
  • 이 단계의 시간 복잡도에 따라 결정
  • 다항식 시간 걸리면, 문제 A도 다항식 시간에 해결됨
• 문제 B의 해를 문제 A의 해로 변환하는 시간
  • 다항식 시간

NP-완전 문제 특성

추이 관계

• A -> B -> C,
  • A -> C
• NP-완전 문제들 중에서 어느 한 문제만 다항식 시간에 해결되면, 모든 다른 NP-완전 문제들이 다항식 시간에 해결됨!

NP-하드 문제 집합

NP-하드 문제

• 어느 문제 A에 대해서, 만일 모든 NP 문제가 문제 A로 다항식 시간에 변환이 가능할 때, 문제 A

문제 집합 사이 관계

• NP-완전 문제는 NP-하드 문제이면서 NP 문제
  

  

NP-완전 문제

문제 A가 NP-완전 문제가 되려면,

• 문제 A는 NP 문제
• 문제 A는 NP-하드 문제

 

 

 

 

 

 

 

 

Reference
https://gazelle-and-cs.tistory.com/74 [Gazelle and Computer Science]