■ NP-완전성과 변환성 - NP-완전성(completeness) 이론은 다항식 시간의 알고리즘을 개발하지 못한 문제들의 성질을 규명하려는 노력의 결과이다. - NP-완전성 이론은 지난 수십년간 가장 중요한 이론적 발전의 하나로 다항식 시간 알고리즘을 개발하지 못하는 많은 문제들이 서로 계산적으로 연관을 가진다는 사실을 입증하였다. ■ 비결정론적(nondeterministic) 알고리즘 - 연산의 결과가 유일하게 정의되는 알고리즘을 결정론적 알고리즘이라함 - 알고리즘의 결과가 유일하지 않은 연산을 가질 수 있도록, 즉, 연산결과의 집합 중 하나를 선택할 수 있도록 허용한 알고리즘을 비결정론적 알고리즘이라 한다. 이 알고리즘에서는 다음 3개의 연산을 추가로 허용한다.
- 예를 들면 x=choice(1..n)이라는 연산을 수행하면 연산결과로 x는 [1..n]의 임의의 정수 값을 갖게 된다. choice(S) 연산의 특성은 만일 알고리즘을 성공적으로 수행하는 선택이 있을 경우는 항상 그 선택 중 하나를 택하여 알고리즘을 성공적으로 끝내며, 그러한 선택이 없을 경우에만 실패로 끝내게 된다. ⑴,⑵,⑶의 계산시간은 O(1)이다. ▶ (예제) A[0..n-1]에서
x를 찾는 비결정론적 알고리즘 ------------------------------------------------------------------- j = choice(0..n-1) if ( A(j)=x ) {printf(j); success;} printf ('-1'); failure ------------------------------------------------------------------- - choice(S) 연산을 행할 수 있는 기계는 현실적으로 존재하지 않는다. 그러나 무제한 병렬성이 허용된다면 choice() 함수가 수행될 때, 각 선택 결과마다 하나의 처리기(processor)를 할당하여 각 선택 결과를 선택하여 계산을 진행하게 하여 서로 다른 처리기가 각 선택 결과를 가지고 병렬적으로 수행하여 이들 중에서 가장 먼저 성공적으로 종료하는 처리기가 다른 모든 처리기의 계산을 끝내게 하는 방법이 있을 수 있다. - 비결정론적 알고리즘에서 Choice() 함수는 매번 선택을 해야할 때마다 주어진 선택 가능한 집합으로부터 성공적인 원소를 선택하는 능력을 갖는다. ▶ (예제) 비결정론적 CNF만족성 알고리즘(E, n) ------------------------------------------------------------------- /* 입력 : E : 논리식 n : 논리식 내의 서로 다른 논리 변수의 수 출력 : 논리식이 참이 될 수 있는 경우 성공 아니면 실패 주어진 논리식 E가 참이 될 수 있는지 결정 */ { boolean x[n]; for ( i = 1; i <= n; i++ ) { x[i] = choice (true, false); } if ( E(x[1], ..., x[n]) == true ) success; else failure; } ------------------------------------------------------------------- |
