[알고리즘] 14. P-NP 문제와 알고리즘의 내일

 

1. 다항시간 알고리즘의 뜻

1) Polynomial-Time Algorithm

최악의 경우 시간복잡도의 상한을 다항함수 꼴로 표현할 수 있는 알고리즘

 

 

2) P-문제  Polynomial

문제에 대한 해를 도출하는 다항시간 알고리즘이 하나 이상 존재하는 경우

예) 정렬 문제

 

 

3) NP-문제 Non-deterministic Polynomial

문제에 대한 해를 검증하는 다항시간 알고리즘이 하나 이상 존재하는 경우

예시) 정수 N개 집합에서 부분집합의 합이 k인 부분집합 찾기

모든 부분 집합의 개수 2^N 다 확인해야함 -> O(2^N)

 

검증한다 : 정수 N개 집합에서 부분집함의 합이 0이 되는 부분집합이 있는가? 의 질문에 {5, -5}로 다항 시간 내 OX 판정 가능한가?

-> 가능. O(1)

{5, 2} 로 판정가능한가? -> 불가능

 

 

해를 얻었다는 것은 그 해에 대한 검증이 이미 끝났다는 것을 의미

-> 모든 P-문제는 NP-문제의 부분집합

 

2. P-NP 문제의 이해

정의로부터 P-문젠는 NP-문제의 부분집합

그렇다면 1) P!=NP 이거나 2) P=NP

 

1) P != NP

(1) NP-하드 문제

다음 조건을 만족하는 X는 NP-하드 문제

NP클래스에 속하는 모든 문제를 다항시간 내에 X문제로 환원시킬 수 있음

NP-문제를 다항시간 다항시간 내에 X문제로 환원시킨 문제이므로 이름 처럼 NP-문제 보다 어려운 문제라고 생각하면 쉬움

 

(2) NP-완전 문제

NP-문제이면서 NP-난해 문제인 모든 문제

 

2) P=NP 

아직은 인간이 문제를 푸는 알고리즘을 찾지 못했다

 

 

 

acm 에서 조사 결과 P=NP라고 2002, 2012년에 9%, P!=NP라고 2002년 61%, 2012년 83% 가 그렇게 생각한다고 설문에 답했다.