[최적화] NP-hard 문제란 무엇일까?

"NP-hard"는 계산 이론에서 문제의 난이도를 분류할 때 사용되는 용어 중 하나입니다. 그렇다면 NP-hard의 정의를 이해하기 위해 몇 가지 기본 용어와 개념을 알아보겠습니다:

1. 결정 문제 (Decision Problem): 주어진 입력에 대해 "예" 또는 "아니오"로 답을 할 수 있는 문제입니다.
2. P (Polynomial time): 모든 결정 문제들의 집합 중에서 다항 시간 안에 해결될 수 있는 문제들의 집합입니다. 다시 말해, 이 문제들은 크기가 (n)인 입력에 대해 (O(n^k))의 시간복잡도를 가지는 알고리즘으로 해결될 수 있습니다.
3. NP (Nondeterministic Polynomial time): 모든 결정 문제들의 집합 중에서 주어진 "예"의 해답(증언, 증거)을 다항 시간 내에 검증할 수 있는 문제들의 집합입니다.

이제 NP-hard에 대해 알아봅시다:

• NP-hard (Nondeterministic Polynomial-time hard): NP 클래스에 속하는 모든 문제가 다항 시간 내에 특정 문제로 환원될 수 있는 그 문제를 의미합니다. 다시 말해, 만약 NP-hard 문제를 다항 시간 안에 해결할 수 있는 방법을 찾는다면, 그 방법을 사용하여 NP의 모든 문제도 다항 시간 안에 해결할 수 있게 됩니다. NP-hard 문제는 NP 문제보다 더 어려울 수도 있고, 심지어 결정 문제로 표현되지 않을 수도 있습니다.

간단한 예로는 외판원 문제 (Traveling Salesman Problem, TSP)이 NP-hard 문제로 알려져 있습니다.

마지막으로, NP-hard와 비슷한 용어로 NP-complete라는 것이 있습니다. NP-complete 문제는 NP-hard이면서 NP에도 속하는 문제를 의미합니다.