15 / 16강

어려운 문제와 근사해

여행할 도시의 순서를 누군가 알려주면 총거리를 계산하기는 쉽습니다. 하지만 가능한 모든 순서 가운데 가장 짧은 것을 찾으려면 일이 훨씬 커질 수 있습니다. 답을 확인하기 쉬운 것과 답을 찾기 쉬운 것은 다릅니다.

P와 NP의 뜻

여기서는 답이 예 또는 아니오인 결정 문제를 기준으로 말합니다.

• P: 입력 길이에 대한 다항 시간 안에 풀 수 있는 문제의 집합입니다.
• NP: 답이 ‘예’일 때, 적절한 증거를 주면 다항 시간 안에 확인할 수 있는 문제의 집합입니다.
• NP-hard: NP의 모든 문제를 다항 시간 변환으로 이 문제에 옮길 수 있는 어려움의 기준입니다. 반드시 NP에 속하지는 않습니다.
• NP-complete: NP에 속하면서 NP-hard인 문제입니다.

P는 NP에 포함됩니다. 둘이 같은지는 아직 해결되지 않았습니다. NP를 ‘풀 수 없는 문제’나 ‘지수 시간이 반드시 필요한 문제’라고 정의하면 안 됩니다. Clay Mathematics Institute의 P vs NP 설명에서도 이 미해결 질문을 다룹니다.

실무에서 선택할 수 있는 방법

입력이 작으면 완전 탐색이나 가지치기로 정확한 답을 구합니다. 특별한 입력 구조를 활용할 수도 있습니다. 큰 입력에서는 요구를 조정해 좋은 답을 빨리 구하는 방법을 검토합니다.

근사 알고리즘은 최적해와 얼마나 차이 날 수 있는지 수학적 보장이 있습니다. 경험적으로 잘 작동하는 휴리스틱은 같은 보장을 반드시 갖지는 않습니다.

예를 들어 무방향 그래프의 모든 간선을 덮는 정점을 고르는 문제에서, 아직 덮지 않은 간선 하나의 양끝을 고르고 연결된 간선을 지우는 일을 반복할 수 있습니다. 고른 간선끼리는 끝점을 공유하지 않으므로 최적해도 간선마다 적어도 한 정점이 필요합니다. 우리는 두 개씩 고르므로 정점 수가 최적해의 2배를 넘지 않습니다.

무작위성은 별도 선택입니다

무작위 선택을 쓰는 알고리즘도 있습니다. 몬테카를로 방식은 일정 확률의 오류를 허용할 수 있고, 라스베이거스 방식은 답의 정확성을 유지하면서 수행 시간이 달라질 수 있습니다. 근사, 무작위, 휴리스틱은 같은 뜻이 아닙니다.

확인 문제

최소 비용 문제에서 ‘항상 최적값의 2배 이하’라는 보장을 얻었습니다. 최적값이 10일 때 반드시 20을 반환한다는 뜻일까요?