NP 완비 NP-complete
요약하자면, 현실적인 시간 내에 답을 얻을 수 있는 해법이 존재하는 것을 말한다.
여기서 이제까지 다룬 모든 알고리즘은 다항식 시간, 즉 입력 크기가 n일 때 최악의 경우에도 수행시간이 O(n^k)의 시간이 걸리는 알고리즘들이었다. 하지만 모든 문제를 컴퓨터로 다항식 시간에 풀 수 있지 않다. 정확히는 풀 수 있으나 현실적인 시간 내에 풀 수 없는 문제가 있고, 아무리 시간이 주어져도 풀 수 없는 문제가 존재한다. 간혹 들어보는 표현 중에 "슈퍼 컴퓨터로 몇 십년 이상 걸리는 문제"가 그것이다.
P 는 polynomial이란 의미로, 문제가 주어졌을 때, 대답을 다항식 시간에 할 수 있는 문제이다. NP는 yes라는 근거만 주어지면 다항식 시간에 풀 수 있는 문제이다.
NP-완비 문제 중 몇 가지는 표면적으로 P문제와 유사해보이는데 최단 단순 경로와 오일러 경로(모든 간선을 한 번씩 방문하고 돌아오는 경로)는 P, 최장 단순 경로와 해밀토니안 싸이클(모든 정점을 한 번씩 방문하고 돌아오는 경로)은 NP-완비다.
결론적으로, 어떤 문제가 NP-완비나 NP-hard라는 확신이 있다면 주어진 시간과 예산 안에서 최대한 좋은 해를 구하는 알고리즘을 개발하는 것이 낫다. 즉 근사해를 구하란 의미다.
728x90
반응형
'공부한 기록 > 알고리즘' 카테고리의 다른 글
| 알고리즘(16) - 문자열 매칭 (0) | 2023.06.08 |
|---|---|
| 알고리즘(15) - 그리디 알고리즘 greedy algorithm (0) | 2023.06.07 |
| 알고리즘(14) - 그래프 (0) | 2023.05.24 |
| 알고리즘(13) - 동적 프로그래밍 dynamic programming (0) | 2023.05.17 |
| 알고리즘(12) - 집합의 처리 (4) | 2023.05.08 |