[Advanced] 12. NP-Complete - 이론편

P와 NP

P : 다항식 시간 알고리즘이 존재하는 모든 결정 문제의 집합

NP : 다항식 시간 비결정적 알고리즘으로 해결할 수 있는 모든 결정 문제의 집합

어떤 문제들이 어려운 문제일까요?

• 다항식 시간이 필요하면 현실적인 시간
• 지수시간 이상이 필요하면 비현실적인 시간으로 "어려운 문제"에 해당 → 다루기 힘든(Intractable) 문제

 

문제의 분류

1. 다항식 시간 알고리즘을 찾은 문제
2. 다루기 힘들다고 증명된 문제
3. 다루기 힘들다고 증명되지 않았고, 다항식 시간 알고리즘도 찾지 못한 문제

 

1. 다항식 시간 알고리즘을 찾은 문제

다항식 시간이 아닌 알고리즘도 있으나, 다항식 시간 알고리즘을 찾은 경우

정렬문제	O(nlogn)	P(Polynomial) 문제 집합
정렬된 배열 검색	O(logn)
행렬 곱셈	O(n^2.3728639)
최단 경로
최소 비용 신장 트리 (MST)
연쇄 행렬 곱셈 문제

 

2. 다루기 힘들다고 증명된 문제

비다항식(Nonpolynomial) 크기의 결과를 요구하는 비현실적인 문제

모든 해밀토니안 회로를 결정하는 문제 (n-1)!	Nonpolynomial
결정 불가능한 문제

 

3. 다루기 힘들다고 증명되지 않았고, 다항식 시간 알고리즘도 찾지 못한 문제

0-1 배낭 문제	NP(Nondeterministic Polynomial) 문제 집합
순회 외판원 문제
그래프 색칠하기 문제
해밀토니안 회로 문제

 

 

최적화 문제와 결정 문제

최적화 문제	결정 문제
최적의 해를 찾는 문제 ex) 그래프 G에서 길이가 가장 짧은 해밀토니안 경로는?	대답이 "예" 또는 "아니오"로 제한된 문제 ex) 그래프 G에서 길이가 k이하인 해밀토니안 경로가 존재?

• 어떤 최적화 문제에 대해서 다항식 시간 알고리즘이 있다면, 그 알고리즘으로부터 그 문제에 해당하는 결정문제에 대한 다항식 시간 알고리즘을 쉽게 유추할 수 있다.
• 즉, P와 NP를 다룰 때 결정 문제만 고려해도 됨