P와 NP

1. P class

입력에 대한 다항시간(polynimial time)에 해결가능한 결정적인 알고리즘을 P class 문제라고 한다.

결정적인 알고리즘은 특정한 값에 대해 정해진 값이 나오는 알고리즘.

 

2. NP class

입력에 대한 다항시간에 해결가능한 비결정적인 알고리즘을 NP class 문제라고 한다.

비결정적 알고리즘은 동일한 입력이 주어지더라도 매번 다른 과정을 통해 다른 결과를 도출하는 알고리즘.

즉, 운에 따라 다항시간에 해결할 수도 있는 알고리즘들을 뜻한다.

보통 답에 대한 '힌트'가 주어질 때 해당 힌트를 사용하여 다항시간 내에 답을 검산할 수 있는 알고리즘을 NP class 문제라고 하기도 한다.

 

{-2, 10, 6, -5, -3} 이라는 집합이 있을 때 이 집합의 부분집합 중 원소의 합이 0이 되는 부분집합이 있는가?

1) 결정적 알고리즘을 사용하면 모든 부분집합에 대하여 원소의 합을 구해보아야 한다.

원소가 n개인 집합의 부분집합은 2^n개(지수시간)이므로 이 문제는 다항시간에 해결가능하지 않으므로 P class에 속하지 않는다.

2) 비결정적 알고리즘을 사용하면 우연히 {-2, 10, -5, -3}이라는 입력이 들어왔을때 덧셈 연산만으로 해당 문제가 True라는 결론을 낼 수 있다.

이러한 우연한 입력에 대하여 다항시간에 해결이 가능하므로 해당 문제는 NP class에 속한다.

3) 답이 True이고 이에 대한 힌트가 {-2, 10, -5, -3}로 주어졌을때 우린 덧셈 연산만으로 답이 True임을 검산할 수 있다.

따라서 해당 문제는 NP class에 속한다.

 

2-1. NP-난해

모든 NP 문제를 다항 시간 내에 'A'문제로 환원이 가능할 때,

이러한 A문제를 NP-난해 라고 부른다.

 

2-2. NP-완전

NP-난해임과 동시에 NP인 문제.