NP - 완전 문제 근사 알고리즘

NP-완전 

- NP 집합에 속하는 결정 문제 중에서 가장 어려운 문제의 부분집합 , 모든 NP 문제를 다항시간 내에 NP-완전 문제로 환산 가능.

- NP-완전 문제 중 하나라도 P에 속한다는 것을 증명하면 모든 NP 문제가 P에 속하기 때문에 P-NP 문제가 P=NP의 형태로 풀림.

- 반대로 NP-완전 문제 중의 하나가 P에 속하지 않는다는 것이 증명된다면 P=NP에 대한 반례가 되어서 P-NP 문제는 P#NP 가됨.

쉬운 문제와 어려운 문제 

판정 문제와 최적화 문제 가 있다.

쉬운 문제	다항식 시간 알고리즘이 존재하는 문제
어려운 문제	다항식 시간을 초과하는 문제

판정 문제	문제의 해가 '예/아니오'로 나오는 문제
최적화 문제	최소치나 최대치를 구하는 형태의 문제

NP-완전성과 변환성 

결정론적 알고리즘

모든 연산의 결과가 유일하게 정으된 것.

비결정론적 알고리즘

알고리즘의 결과가 유일하지 않은 연산을 가질 수 있도록, 지정된 연산 결과의 집합 중 하나를 선택할 수 있도록 허용.

- choice(X) : 집합 X의 원소 중 하나를 임의로 선택함. 

- failure : 알고리즘이 실패로 끝났음을 알린다.

- success : 알고리즘이 성공적으로 끝났음을 알림.

- choice 연산을 구현할 수 있는 방법은 무제한적인 병렬성을 허용해 여러 개의 처리기가 여러 복사본을 동시에 수행해 이들 중

 먼저 성공적으로 종료하는 처리기가 다른 모든 계산을 끝내게 하면 됨.

- choice 함수는 매번 선택할 때마다 주어진 선택 가능한 집합으로부터 성공적인 원소를 선택하는 능력 가짐.

2. P, NP의 정의

P - 결정론적 알고리즘에 의해 다항식 시간에 풀 수 있는 모든 판정 문제 집합

NP - 비결정론적 알고리즘에 의해 다항식 시간에 풀 수 있는 모든 판정 문제 집합

1.  비결정론적 의미 - 여러 가지 중에서 하나를 택해야 할 때 스스로 최선의 선택을 할 수 있는 능력.

 2. NP 문제 - 여러 경우에서 선택해야 하는 경우 스스로 최선의 선택을 하여 다항식 시간에 풀 수 있는 것.

3. 다항식 시간 변환

문제 B에 대한 알고리즘으로 문제 A를 풀 수 있을 때, 문제 A를 문제 B로 변환할 수 있음. 이러한 변환에 다항식 시간 소요됨.

다항식의 합이나 곱은 다항식이고 성질은 추이적이고, 다항식 시간 복잡도는 다항식 시간으로 유지됨.

4. 완전 문제

어떤 부류에 속하는 모든 문제가 그 부류에 속하는 어떤 문제 R로 다항식 시간 변환에 가능한 문제를 말함.

그 부류의 다른 모든 문제도 다항식 시간에 풀 수 있음.

5. 하드 문제

어떤 부류의 모든 문제가 문제 R로 다항식 시간에 변환될 수 있지만 R가 그 부류에 속한다는 조건이 없으면 R은 부류에 속함.

그 부류에 속하는 어떤 문제보다도 풀기 어렵다.

6. NP-하드

NP의 모든 문제가 어떤 문제 A로 다항식 시간이 변환됨.

7. NP-완전

A가 NP에 속한다면 그 문제는 NP-완전

클리크 판정 문제(CDP)

클리크 - 그래프 G=(V, E)의 완전 부분 그래프를 말함. 완전 그래프란 모든 정점ㅈ 사이에 간선이 있는 그래프!

클리프 판정 문제 - 그래프 G와 정수K가 주어졌을 때 G의 크기가 K인 클리크를 갖는지 여부를 판정하는 문제.

버텍스 커버 문제(VCP)

버텍스 커버 - 정점의 부분집합으로, 모든 간선이 최소한 이들 정점 중 하나 이상에 부수해야 함.

버텍스 커버 문제 - 주어진 그래프 G의 최소 버텍스 커버를 찾는 문제. 이를 판정 문제로 변환하면, 주어진 그래프 G가 크기

K인 버텍스 커버를 갖느냐는 문제.

VCP는 NP- 완전 문제임.

해밀토니언 사이클 문제(HCP)

- 무방향 그래프 G가 주어졌을때 G가 해밀토니언 사이클을 갖느냐는 문제.

- 그래프 G의 한 정점 A에서 출발하여 모든 정점을 한 번 통과한 후 a로 다시 되돌아오는 경로.

해밀토니언 사이클을 찾는 직선적 알고리즘은 n!개의 경로를 하나씩 검사하여 대상경로가 해밀토니언 사이클이 되는지

확인. 시간복잡도 O(n!)

HCP 는 NP - 완전문제.

CNF 문제

CNF 만족성 문제는 연결된 정규 곱형으로 주어진 논리식의 리트럴들에 참 또는 거짓 값들을 적절히 지정하여 전체 논리식의

값을 참으로 만들 수가 있는 것.

리트럴 - 논리 변수 XI 또는 그 부정형 XI를 말함

 배낭 문제 

최적화 문제 결정 문제로 구분

- FPTAS 오스카 이바라 , 김철언 1975년 개발.

- 짐을 쪼갤 수 있으면 분할가능 배낭 문제 , 없다면 0/1 배낭 문제 동적계획법 적용.

NP -완전 문제

실용적 접근 방법.

 - 대부분의 입력에 대해 최적해를 구할 수 있는 효율적인 다항식 시간 알고리즘

- 적용될 수 있는 입력 크기가 보다 더 커진 보다 더 효율적인 지수 시간 알고리즘

- 최적에 가까운 준최적해를 구하는 효율적인 다항식 시간 알고리즘