NP 알고리즘은 해를 찾는 알고리즘이 아니라, 해를 다항식 시간에 확인하는 알고리즘이다.
어느 문제 A에 대해서, 만일 모든 NP문제가 문제 A로 다항식 시간에 변환이 가능하다면, 문제 A는 NP-하드 문제이다.
문제 A가 NP-완전문제가 되려면
1. NP-하드문제이면서
2. 동시에 NP문제이다.
NP-완전문제는
1. 다항식 변환 가능.
2. 다항식 시간에 해 발견 불가
3. NP-하드 문제임(다항식 시간으로 변형 가능)
4. NP문제이다.
'📈알고리즘 > 알고리즘' 카테고리의 다른 글
| 외부정렬 (0) | 2023.05.30 |
|---|---|
| 근사 알고리즘(2) 작업 스케줄링 문제, 클러스터링 문제 (0) | 2023.05.24 |
| 근사 알고리즘(1)[여행자 문제, 정점 커버 문제, 통 채우기 문제] (0) | 2023.05.22 |
| 휴리스틱 flow shop 사례로 이해해보기 (0) | 2023.05.22 |
| 유전자 알고리즘 이해해보기 (0) | 2023.05.17 |