| NP 완전 문제 | 여러 가지 NP 완전문제 | NP-완전성과 변환성 |

■ 쉬운(tractable)문제와 어려운(untractable)문제

• 쉬운(tractable)문제 : k가 상수일 때 O(N^k)의 다항식 시간 알고리즘이 존재하는 문제

• 어려운(untractable)문제 : 그 문제를 해결하는 데 다항식시간보다 더 많은 시간을 요구하는 문제

■ NP 완전(Non-deterministic Polynomial-time Complete) 문제

• 다항식 시간 알고리즘이 아직 만들어지지도 않았고, 그러한 알고리즘이 존재하지 않는다고 증명되지도 않은 문제이다. 지금까지 광범위한 부류의 문제가 NP-완전인 것으로 증명되었으며, NP-완전 문제 중의 어느 한 문제라도 다항식 시간 알고리즘이 발견되면 다른 모든 NP-완전 문제도 다항식 시간에 풀릴 수 있다. NP완전 문제에 대한 효율적인 알고리즘은 몇 십년에 걸쳐서 연구되었으나 아직도 효율적인 알고리즘이 발견되지 않은 점으로 미루어 대부분의 학자들은 NP-완전 문제는 어려운 문제일 것으로 믿고 있다.
• 따라서 현명한 알고리즘 설계자라면, 일단 NP-완전 문제를 만나면 그 문제에 대한 정확한 해를 효율적으로 구하는 알고리즘 설계하는 노력을 포기하고, 대신 근사해를 구하는 효율적인 알고리즘을 만드는 것이 보다 현실적이다.

■ 판정(decision)문제와 최적화(Optimization)문제

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

▶ 외판원 문제

- 최적화 문제 : 가중치가 있는 방향 그래프에서, 한 정점에서 출발하여 다른 모든 정점을 정확히 한번씩만 방문하면서 출발점으로 돌아오는 일주 여행 경로 중에서 총 여행거리가 최소가 되는 경로를 구하시오.

- 결정 문제 : 어떤 야수 d가 주어지고, 총 일주여행거리가 d를 넘지 않는 경로가 있는지 없는지를 결정하시오.

▶ 0-1 배낭채우기 문제

- 최적화 문제 : 배낭에 넣을 아이템의 무게와 가치를 알고 있을 때, 용량이 W가 되는 배낭에 아이템을 총 이익이 최대가 되도록 채우시오.

- 결정 문제 : 용량이 W가 되는 배낭에 아이템을 총 이익이 최소한 P가 되도록 채울 수 있는지를 결정하시오.