NP-완전성 (NP-Completeness)
쉽게 풀면
직소 퍼즐을 생각해보세요. 누군가 완성된 그림을 보여주면 "이게 맞는 조각 배치인지" 확인하는 건 한눈에 금방 됩니다. 하지만 처음부터 수천 조각을 직접 맞춰서 완성하려면 엄청난 시간이 걸립니다. NP-완전 문제들이 딱 이런 성격입니다. 누군가 "답은 이거야"라고 후보를 하나 던져주면 그게 맞는지 빠르게 검산할 수 있지만, 후보 없이 처음부터 정답을 계산해내려면 문제 크기가 커질수록 시간이 기하급수적으로 늘어납니다. 더 흥미로운 점은 이런 문제들이 서로 친척 관계라서, 그중 단 하나라도 빠르게 푸는 방법을 찾으면 나머지 모든 NP-완전 문제도 한꺼번에 빠르게 풀 수 있게 된다는 것입니다(다만 아직 그런 방법은 발견되지 않았습니다).
왜 중요한가
어떤 문제가 NP-완전임을 증명하는 것은 그 문제에 대해 다항 시간 내에 정확한 해를 구하는 알고리즘을 찾으려는 시도가 헛수고일 가능성이 높다는 것을 이론적으로 보여주는 것이므로, 알고리즘·최적화 연구에서 문제의 난이도를 정당화하고 근사 알고리즘이나 휴리스틱 접근을 선택하는 근거로 삼는 데 필수적입니다. 또한 P와 NP가 같은지 다른지를 묻는 P-NP 문제는 이론 컴퓨터과학에서 가장 중요한 미해결 문제 중 하나로, 암호학의 안전성 근거와도 깊이 연결되어 있습니다.
논문에서는 이렇게 쓰입니다
이 문장은 다루는 문제가 이론적으로 매우 어려운 부류에 속하기 때문에, 완벽한 정답을 구하는 대신 충분히 좋은 근사값을 빠르게 찾는 전략을 택했다는 뜻입니다. 스케줄링, 경로 최적화, 자원 배분 등 조합 최적화 문제를 다루는 논문에서 문제의 난이도를 정당화할 때 자주 등장합니다.
이론 컴퓨터과학 논문에서 새로운 문제의 난이도를 증명할 때 기존에 알려진 NP-완전 문제로부터 환원을 구성하는 전형적인 방식을 보여주는 예문입니다.
네트워크 공학 분야에서 NP-완전성을 근거로 실용적인 휴리스틱 알고리즘 개발의 필요성을 설명하는 예문입니다.
조금 더 깊게 보면
어떤 문제가 NP-완전임을 증명하는 표준적인 방법은 이미 NP-완전임이 알려진 문제(예: SAT, 3-SAT, 정점 커버, 해밀턴 순환)를 다항 시간 안에 그 문제로 환원(reduction)할 수 있음을 보이는 것입니다. 이렇게 서로 환원 가능한 문제들의 집합을 다루기 때문에, 하나의 NP-완전 문제에 대한 다항 시간 알고리즘 발견은 곧 모든 NP-완전 문제의 해결로 이어집니다. 실무에서는 정확해 대신 근사 비율이 보장된 근사 알고리즘, 특정 입력 구조에서만 빠르게 동작하는 매개변수화 알고리즘, 또는 유전 알고리즘·시뮬레이티드 어닐링 같은 메타휴리스틱을 활용해 현실적인 시간 내에 충분히 좋은 해를 구하는 경우가 많습니다.
주의할 점
NP-완전 문제라고 해서 "풀 수 없다"는 뜻은 아닙니다. 문제 크기가 작으면 정확한 답을 구할 수 있고, 크기가 커져도 탐욕 알고리즘이나 근사 알고리즘, 휴리스틱을 쓰면 완벽하지는 않아도 실용적인 답을 빠르게 얻을 수 있습니다. 또한 NP-완전은 "NP에 속하면서 동시에 가장 어려운 문제"를 뜻하므로, 모든 어려운 문제가 NP-완전인 것도 아닙니다.