NP-난해 문제 (NP-hard problem)

한 줄 정의: NP에 속한 모든 문제가 다항 시간에 환원될 수 있을 만큼 어려운 문제로, 반드시 NP에 속할 필요는 없는 문제.

쉽게 풀면

NP-난해 문제는 NP-완전 문제보다 넓은 개념이다. NP에 속한 모든 문제만큼 어렵거나 그보다 더 어려운 문제를 통칭하며, 답을 다항 시간에 검증조차 할 수 없는 문제도 포함된다. 예를 들어 최적화 문제(가장 짧은 경로가 아니라 '최적값이 정확히 얼마인가')는 종종 검증 자체가 어려워 NP-완전이 아니라 NP-난해로 분류된다.

왜 중요한가

실제 공학·산업 문제 중 상당수는 "예/아니오"로 답하는 결정 문제가 아니라 "최적값이 무엇인가"를 묻는 최적화 문제 형태로 나타나며, 이런 문제는 검증 자체가 어려워 NP-완전보다 넓은 NP-난해로 분류되는 경우가 많습니다. 따라서 알고리즘 논문에서 다루는 문제가 NP-난해임을 밝히는 것은 정확해를 포기하고 근사 알고리즘이나 휴리스틱을 택하는 연구 설계를 정당화하는 핵심 근거가 됩니다.

논문에서는 이렇게 쓰입니다

"본 최적화 문제는 결정 버전이 NP-완전이므로, 최적화 버전 자체는 NP-난해로 간주된다."

결정 문제 형태가 아닌 최적화 문제의 난이도를 논할 때 NP-난해라는 표현이 흔히 쓰인다.

"차량 경로 최적화 문제는 NP-난해로 알려져 있어, 본 연구는 유전 알고리즘 기반의 근사 해법을 제안한다."

물류 최적화 분야에서 NP-난해성을 근거로 메타휴리스틱 기법을 채택하는 전형적인 예문입니다.

"신경망 구조 탐색은 탐색 공간이 지수적으로 커지는 NP-난해 조합 최적화 문제로 볼 수 있어, 강화학습 기반 탐색 전략을 활용하였다."

기계학습 분야에서 신경망 구조를 자동으로 찾는 문제가 NP-난해 조합 최적화로 다루어지는 예문입니다.

조금 더 깊게 보면

NP-난해는 NP-완전보다 더 넓은 범주로, 정지 문제처럼 결정 불가능한(undecidable) 문제도 NP-난해에 포함될 수 있습니다. 즉 NP-완전이 되려면 그 문제가 NP에 속해야(다항 시간 내 검증이 가능해야) 한다는 추가 조건이 필요하지만, NP-난해는 이 조건 없이 오직 "NP의 모든 문제만큼 어렵다"는 것만 요구합니다. 논문에서 최적화 문제가 NP-난해임을 증명할 때는 흔히 그 문제의 결정 버전(예/아니오 형태로 바꾼 문제)이 NP-완전임을 보이는 방식을 사용합니다.

주의할 점

"모든 NP-완전 문제는 NP-난해지만, 모든 NP-난해 문제가 NP-완전인 것은 아니다"라는 포함 관계를 정확히 구분해야 한다.