NP Hard 및 NP-Complete 클래스

NP에 있고 다음과 같은 경우 NPC 클래스에 문제가 있습니다. hardNP의 문제로. 문제는NP-hard NP의 모든 문제가 NP 자체에 있지 않더라도 다항식 시간을 줄일 수 있다면.

이러한 문제에 대해 다항식 시간 알고리즘이 존재하는 경우 NP의 모든 문제는 다항식 시간을 풀 수 있습니다. 이러한 문제를NP-complete. NP 완전성 현상은 이론적 이유와 실제적 이유 모두에서 중요합니다.

NP- 완전성의 정의

언어 B 이다 NP-complete 두 가지 조건을 만족한다면

B NP에 있음
마다 A NP에서 다항식 시간은 B.

언어가 두 번째 속성을 충족하지만 반드시 첫 번째 속성이 아닐 경우 언어는 B 로 알려져 있습니다 NP-Hard. 비공식적으로 검색 문제B 이다 NP-Hard 존재한다면 NP-Complete 문제 A Turing이 B.

NP-Hard의 문제는 다항식 시간으로 풀 수 없습니다. P = NP. 문제가 NPC로 판명되면 효율적인 알고리즘을 찾는 데 시간을 낭비 할 필요가 없습니다. 대신 디자인 근사 알고리즘에 집중할 수 있습니다.

NP- 완전한 문제

다음은 다항식 시간 알고리즘이 알려지지 않은 몇 가지 NP-Complete 문제입니다.

그래프에 해밀턴주기가 있는지 확인
부울 공식이 만족 스러운지 여부 등을 결정합니다.

NP- 어려운 문제

다음 문제는 NP-Hard입니다.

회로 만족도 문제
세트 커버
정점 커버
여행하는 세일즈맨 문제

이 맥락에서 TSP는 NP-Complete입니다.

TSP는 NP-Complete입니다.

여행하는 세일즈맨 문제는 세일즈맨과 일련의 도시로 구성됩니다. 판매원은 특정 도시에서 시작하여 같은 도시로 돌아가는 각 도시를 방문해야합니다. 문제의 문제는 여행하는 세일즈맨이 여행의 총 길이를 최소화하려고한다는 것입니다.

증명

를 입증하기 위해 TSP is NP-Complete, 먼저 우리는 TSP belongs to NP. TSP에서 둘러보기를 찾고 둘러보기에 각 꼭지점이 한 번씩 포함되어 있는지 확인합니다. 그런 다음 둘러보기 가장자리의 총 비용이 계산됩니다. 마지막으로 비용이 최소인지 확인합니다. 이것은 다항식 시간에 완료 될 수 있습니다. 그러므로TSP belongs to NP.

둘째, 우리는 TSP is NP-hard. 이를 증명하기 위해 한 가지 방법은Hamiltonian cycle ≤_p TSP (해밀턴주기 문제가 NPcomplete라는 것을 알고 있습니다).

취하다 G = (V, E) 해밀턴 사이클의 한 예입니다.

따라서 TSP의 인스턴스가 구성됩니다. 완전한 그래프를 만듭니다.G^' = (V, E^'), 어디

$$ E ^ { '} = \ lbrace (i, j) \ colon i, j \ in V \ : \ : and \ : i \ neq j $$

따라서 비용 함수는 다음과 같이 정의됩니다.

$$ t (i, j) = \ begin {cases} 0 & if \ : (i, j) \ : \ in E \\ 1 & else \ end {cases} $$

자, 해밀턴 사이클이 h 에 존재 G. 각 에지의 비용이h 이다 0 에 G^' 각 모서리가 속하므로 E. 따라서,h 비용이있다 0 에 G^'. 따라서 그래프G 해밀턴 사이클이있는 경우 그래프 G^' 투어가있다 0 비용.

반대로, 우리는 G^' 투어가있다 h^' 최대 비용 0. 가장자리 비용E^' 아르 0 과 1정의에 따라. 따라서 각 모서리에는 다음과 같은 비용이 있어야합니다.0 비용으로 h^' 이다 0. 따라서 우리는h^' 가장자리 만 포함 E.

따라서 우리는 G 해밀턴 사이클이 있습니다. G^' 기껏해야 비용 둘러보기 0. TSP는 NP 완전합니다.