NP-완전 (r1)

NP 클래스는 비결정론적 튜링 기계를 사용하여 다항 시간 내에 답이 '예'인 경우를 검증할 수 있는 모든 결정 문제의 집합이다. 여기서 '검증'이란 어떤 문제의 주어진 후보 해답이 올바른지 확인하는 과정을 의미한다. 예를 들어, 외판원 문제에서 특정 경로가 주어졌을 때, 그 경로의 총 길이가 특정 값 K 이하인지는 다항 시간 내에 쉽게 계산하여 확인할 수 있다. 이처럼 답을 '검증'하는 것은 빠르게 할 수 있지만, 답 자체를 '찾는' 과정은 훨씬 더 어려울 수 있다는 점이 NP 클래스의 특징이다.

NP는 'Nondeterministic Polynomial time'의 약자로, 비결정론적 다항 시간을 뜻한다. 이 개념은 계산 복잡도 이론의 핵심적인 복잡도 종류 중 하나이다. NP에 속하는 문제들은 그 해답을 추측하는 단계와 이를 검증하는 단계로 나누어 생각할 수 있으며, 비결정론적 튜링 기계는 이 추측 단계를 상상 속에서 모든 가능성을 동시에 시도한다고 가정한다. 따라서 실제 계산 시간은 검증에 소요되는 다항 시간으로 정의된다.

NP 클래스에는 우리가 일상에서 접하는 수많은 중요한 최적화 문제와 조합론적 문제들이 포함된다. 대표적으로 충족 가능성 문제, 해밀턴 경로 문제, 외판원 문제 등이 여기에 속한다. 이들 문제의 공통점은 특정 해답이 주어지면 그 적합성을 비교적 빠르게 확인할 수 있지만, 수많은 가능성 중에서 최적의 해답을 찾아내는 일반적인 방법은 아직 알려져 있지 않다는 것이다.

NP 클래스와 P (복잡도) 클래스의 관계는 P-NP 문제라는 미해결 난제의 중심에 있다. P는 결정론적 튜링 기계로 다항 시간 내에 해결할 수 있는 문제들의 집합이다. 모든 P 문제는 자동으로 NP 문제이기도 하다. 왜냐하면 문제를 해결하는 알고리즘이 있다면, 그 알고리즘으로 생성된 해답을 검증하는 것은 당연히 가능하기 때문이다. 그러나 그 반대, 즉 모든 NP 문제가 P에 속하는지는 아직 증명되거나 반증되지 않았다.

다항 시간 변환은 한 결정 문제를 다른 결정 문제로 효율적으로 변환하는 방법이다. 구체적으로, 문제 A의 모든 사례를 문제 B의 사례로 변환하는 다항 시간 알고리즘이 존재할 때, 이를 다항 시간 변환이라고 한다. 이때 변환된 사례의 답은 원래 사례의 답과 동일해야 한다.

이러한 변환은 문제 간의 계산적 난이도를 비교하는 핵심 도구이다. 만약 문제 A가 문제 B로 다항 시간 변환 가능하고, 문제 B를 다항 시간에 해결할 수 있다면, 문제 A도 다항 시간에 해결할 수 있다. 반대로, 문제 A가 해결하기 어렵다고 알려져 있다면, 문제 B 역시 해결하기 어려울 것이라고 추론할 수 있다.

NP-완전성을 증명하는 데 이 개념이 필수적으로 사용된다. 어떤 문제가 NP-완전임을 보이려면, 먼저 그 문제가 NP (복잡도)에 속함을 보이고, 이미 NP-완전으로 알려진 다른 문제를 이 문제로 다항 시간 변환할 수 있음을 증명하면 된다. 스티븐 쿡이 충족 가능성 문제(SAT)의 NP-완전성을 최초로 증명한 이후, 수많은 문제들이 SAT나 다른 NP-완전 문제로부터의 다항 시간 변환을 통해 그 NP-완전성이 입증되었다.

따라서 다항 시간 변환은 복잡도 이론에서 문제들을 난이도에 따라 분류하고, P-NP 문제와 같은 근본적인 질문을 탐구하는 데 기초를 제공한다.

NP-완전의 정의는 계산 복잡도 이론의 핵심 개념 중 하나이다. 어떤 결정 문제가 다음 두 가지 조건을 모두 만족할 때, 그 문제를 NP-완전이라고 한다. 첫째, 그 문제 자체가 NP (복잡도)에 속해야 한다. 즉, 주어진 '예'라는 답에 대한 증거(예를 들어 해밀턴 경로 문제에서의 경로 순서)가 있을 때, 그 증거가 맞는지를 다항 시간 내에 확인할 수 있어야 한다. 둘째, NP에 속하는 *모든* 다른 문제가 그 문제로 다항 시간 내에 변환(환원)될 수 있어야 한다. 이 변환은 문제 A의 임의의 사례를 문제 B의 사례로 바꾸었을 때, 두 사례의 답(예/아니오)이 일치해야 함을 의미한다.

이 정의에 따르면, NP-완전 문제는 NP 클래스 내에서 가장 어려운 문제들의 집합을 형성한다. 만약 하나의 NP-완전 문제를 다항 시간에 해결하는 일반적인 알고리즘이 발견된다면, 다른 모든 NP 문제들도 그 문제로 변환한 후 해결함으로써 다항 시간에 풀 수 있게 된다. 이는 곧 P-NP 문제에서 P=NP가 증명되는 결과를 가져온다. 반대로, 만약 하나의 NP-완전 문제가 본질적으로 다항 시간에 풀 수 없다면, NP의 모든 문제는 P보다 어렵거나 같다는 것이 되며, 이는 P≠NP를 의미하게 된다.

NP-완전성 개념의 초석은 1971년 스티븐 쿡이 충족 가능성 문제(SAT)가 NP-완전임을 증명한 논문에서 비롯되었다. 이후 1972년 리처드 카프는 21개의 다양한 조합 최적화 문제들, 예를 들어 꼭짓점 커버 문제, 해밀턴 경로 문제, 클릭 문제 등이 SAT로부터 다항 시간 변환이 가능함을 보여주어 이들 역시 NP-완전임을 증명했다. 이 작업을 통해 수많은 실용적인 문제들이 서로 연결되어 있으며, 그 근본적인 난이도를 공유한다는 사실이 널리 인식되기 시작했다.

따라서 어떤 새로운 문제가 NP-완전임을 증명하는 일반적인 방법은, 이미 알려진 NP-완전 문제를 선택하여 그것을 새로운 문제로 다항 시간 내에 변환하는 것이다. 이는 새로운 문제가 적어도 기존의 NP-완전 문제만큼은 어렵다는 것을 보여주며, 동시에 그 문제가 NP에 속함을 보이면 NP-완전성 증명이 완료된다.

충족 가능성 문제는 논리 명제의 참 거짓을 결정하는 문제이다. 주어진 명제 논리식이 참이 되도록 각 변수에 참 또는 거짓 값을 할당할 수 있는지 묻는 문제로, 계산 복잡도 이론에서 최초로 NP-완전임이 증명된 대표적인 문제이다. 이 문제는 일반적으로 SAT(Satisfiability Problem)라고 불린다.

충족 가능성 문제는 그 형태에 따라 여러 하위 분류로 나뉜다. 가장 기본적인 형태는 부울 대수 변수와 논리곱(AND), 논리합(OR), 부정(NOT) 연산자로 구성된 일반적인 논리식에 대한 문제이다. 특히 모든 논리식이 논리곱 정규형(CNF) 형태, 즉 절들의 논리곱으로 표현된 경우를 CNF-SAT이라고 한다. CNF-SAT 중에서도 각 절이 정확히 k개의 리터럴(변수나 그 부정)을 포함할 때, 이를 k-SAT 문제라고 한다.

1971년 스티븐 쿡은 그의 획기적인 논문에서 SAT 문제가 NP-완전임을 증명했다[1]. 이 증명은 쿡-레빈 정리로 알려져 있으며, 모든 NP (복잡도) 문제가 SAT 문제로 다항 시간 내에 변환될 수 있음을 보였다. 이로 인해 SAT는 NP-완전 문제의 원형이 되었고, 새로운 문제가 NP-완전임을 증명할 때는 그 문제가 SAT로부터, 또는 이미 NP-완전임이 알려진 다른 문제로부터 다항 시간 변환이 가능함을 보이는 방법이 표준이 되었다.

이 문제의 중요성은 이론적 의미를 넘어 실용적이다. 전자 설계 자동화, 소프트웨어 검증, 인공지능의 계획 문제, 그리고 운영 연구 등 다양한 분야에서 문제를 SAT의 형태로 모델링하여 해결하는 SAT 솔버 기술이 활발히 연구되고 적용되고 있다.

해밀턴 경로 문제는 주어진 그래프에서 모든 정점을 정확히 한 번씩만 방문하는 경로가 존재하는지를 판별하는 결정 문제이다. 이때 시작점과 끝점이 같은 경로, 즉 모든 정점을 한 번씩 지나 시작점으로 돌아오는 경로는 특히 해밀턴 순환 문제라고 한다. 이 문제는 NP에 속하는 것은 비교적 쉽게 확인할 수 있으며, 1972년 리처드 카프가 3-SAT 문제로부터 다항 시간 변환을 통해 이 문제가 NP-난해임을 증명함으로써 NP-완전 문제임이 밝혀졌다.

해밀턴 경로 문제는 이론적 중요성뿐만 아니라 실제 응용 분야에서도 널리 등장한다. 대표적인 예로 운송 네트워크에서 최적의 경로를 찾거나, 집적 회로 설계에서 논리 게이트의 배치를 최적화하는 문제, 생물정보학에서 DNA 서열 조립 문제 등이 해밀턴 경로 문제로 모델링될 수 있다. 특히 모든 도시를 한 번씩만 방문하는 최단 경로를 찾는 외판원 문제는 해밀턴 순환 문제에 비용 최소화 조건이 추가된 형태로 볼 수 있다.

이 문제를 해결하기 위한 정확한 알고리즘으로는 동적 계획법을 활용한 방법이 잘 알려져 있다. 이 알고리즘은 시간 복잡도가 O(n² * 2ⁿ)으로, 정점의 수가 증가함에 따라 실행 시간이 매우 빠르게 증가한다. 따라서 큰 규모의 문제에 대해서는 휴리스틱 알고리즘이나 근사 알고리즘이 사용되기도 하지만, 일반 그래프에 대해서는 좋은 성능의 근사 해법을 찾는 것도 어려운 문제로 알려져 있다.

외판원 문제는 여러 도시를 한 번씩만 방문하고 출발점으로 돌아오는 최단 경로를 찾는 조합 최적화 문제이다. 이 문제는 운용과학과 이론전산학에서 매우 중요한 문제로, 물류 경로 최적화, 회로 기판 배선, 유전체학 등 다양한 분야에 응용된다. 문제의 입력은 도시 간 거리 행렬이며, 목표는 모든 도시를 정확히 한 번씩 방문하는 최단 순회 경로를 찾는 것이다.

외판원 문제의 결정 문제 버전은 "주어진 거리와 비용 한계 K에 대해, 총 이동 거리가 K 이하인 순회 경로가 존재하는가?"로 정의된다. 이 결정 문제는 NP (복잡도)에 속하며, 해밀턴 경로 문제로부터 다항 시간 변환될 수 있어 NP-난해임이 증명되었다. 이후 리처드 카프(Richard Karp)는 1972년 이 문제가 NP-완전임을 보였다. 이는 외판원 문제의 최적해를 다항 시간 내에 찾는 일반적인 알고리즘이 존재하지 않을 가능성이 매우 높음을 의미한다.

외판원 문제는 그 난해함에도 불구하고 실용적 중요성 때문에 다양한 해결 기법이 연구되어 왔다. 정확한 해를 구하는 동적 계획법이나 분기 한정법 같은 알고리즘은 소규모 문제에 적용 가능하다. 대규모 문제의 경우, 근사 알고리즘이나 메타휴리스틱 알고리즘을 사용하여 합리적인 시간 내에 우수한 해를 찾는다. 대표적인 근사 알고리즘으로는 최소 신장 트리를 이용하는 방법이 있으며, 메타휴리스틱으로는 담금질 기법, 유전 알고리즘, 개미 집단 최적화 등이 널리 사용된다.

이 문제는 여러 변형이 존재한다. 대칭 외판원 문제는 도시 간 거리가 양방향으로 동일한 경우이고, 비대칭 외판원 문제는 거리가 방향에 따라 다를 수 있다. 또한, 도시 좌표가 주어지고 유클리드 거리를 사용하는 경우를 유클리드 외판원 문제라고 하며, 이 경우에도 문제는 NP-난해이다. 외판원 문제는 계산 복잡도 이론의 교육과 연구에서 NP-완전 문제의 전형적인 사례로 자주 인용된다.

정수 계획법은 선형 계획법의 특수한 형태로, 모든 결정 변수가 정수 값을 가져야 한다는 조건이 추가된 최적화 문제이다. 선형 계획법은 다항 시간 내에 해결 가능하지만, 정수 조건이 추가되면 문제의 복잡도가 크게 증가한다. 정수 계획법의 결정 문제 버전, 즉 "주어진 정수 계획법 문제에 특정 목적 함수 값 이하의 정수 해가 존재하는가?"를 묻는 문제는 NP-완전으로 알려져 있다.

이 문제는 다항 시간 변환을 통해 잘 알려진 NP-완전 문제인 충족 가능성 문제로 환원될 수 있다. 예를 들어, 논리 회로의 각 게이트를 선형 부등식으로 모델링하고, 회로의 출력값을 목적 함수로 설정함으로써 SAT 문제를 정수 계획법 문제로 표현할 수 있다. 이 변환은 다항 시간 내에 이루어지므로, 정수 계획법의 결정 문제가 NP-난해임을 보여준다. 동시에 주어진 정수 해가 조건을 만족하는지 검증하는 것은 쉽기 때문에 이 문제는 NP에 속하며, 따라서 NP-완전임이 증명된다.

정수 계획법은 현실 세계의 다양한 문제를 모델링하는 데 널리 사용된다. 공장의 생산 계획, 물류 네트워크 설계, 자원 배분, 스케줄링 등에서 결정 변수가 이산적인 값을 가져야 하는 경우가 많기 때문이다. 이러한 문제들은 본질적으로 조합 최적화 문제에 해당하며, 정수 계획법은 이를 공식화하는 강력한 틀을 제공한다.

정수 계획법 문제를 해결하기 위한 주요 알고리즘으로는 분기 한정법이 있다. 이 방법은 가능한 정수 해 공간을 체계적으로 탐색하면서, 선형 계획법 완화를 통해 얻은 경계값을 이용해 탐색 공간을 줄여나간다. 그러나 최악의 경우 해 공간을 거의 모두 탐색해야 할 수 있어, 문제 크기가 커지면 계산 시간이 기하급수적으로 증가할 수 있다. 이는 정수 계획법 문제가 NP-완전이라는 사실과 부합하는 현상이다.

배낭 문제는 조합 최적화 분야에서 매우 유명한 문제이다. 주어진 용량을 가진 배낭과 각각 무게와 가치를 가진 물건들의 집합이 있을 때, 배낭의 용량을 초과하지 않으면서 물건들의 총 가치를 최대화하는 물건들의 부분집합을 선택하는 문제이다. 이 문제의 결정 문제 버전, 즉 "주어진 가치 K 이상을 달성하는 선택이 존재하는가?"라는 질문은 NP-완전에 속한다.

배낭 문제는 실생활에서 자주 접할 수 있는 자원 할당 문제의 전형적인 예시이다. 예를 들어, 투자 포트폴리오 구성, 물류 차량의 적재, 데이터 전송의 패킷 선택 등 다양한 분야에서 유사한 구조를 가진 문제로 변형되어 적용된다. 문제 자체는 이해하기 매우 쉽지만, 이를 최적으로 해결하는 것은 계산상 매우 어려운 것으로 알려져 있다.

이 문제의 NP-완전성을 증명하기 위해서는 일반적으로 알려진 다른 NP-완전 문제로부터의 다항 시간 변환이 사용된다. 예를 들어, 부분집합 합 문제는 배낭 문제의 특수한 경우로 쉽게 환원될 수 있으며, 부분집합 합 문제 자체가 NP-완전이므로 배낭 문제도 NP-완전임이 증명된다.

배낭 문제는 그 실용적 중요성 때문에 다양한 해결 기법이 연구되어 왔다. 정확한 해를 구하는 방법으로는 동적 계획법을 이용한 의사 다항 시간 알고리즘이 잘 알려져 있다. 그러나 이는 물건의 무게나 가치에 의존하므로, 입력 크기(물건의 개수)에 대해서만 다항 시간이라고 할 수 없는 경우가 많다. 따라서 실제로는 근사 알고리즘이나 휴리스틱 알고리즘을 통해 근사해를 구하거나, 특정 매개변수(예: 가치의 범위)가 작을 때 효율적인 매개변수화 알고리즘이 활용되기도 한다.

NP-완전 문제는 정확한 해를 다항 시간 내에 구하는 것이 어렵다고 여겨지기 때문에, 현실적으로는 최적해 대신 '충분히 좋은' 근사해를 효율적으로 찾는 방법이 널리 연구되고 활용된다. 이러한 방법을 근사 알고리즘이라고 한다. 근사 알고리즘은 문제의 최적해와 근사해 사이의 오차 비율, 즉 근사 비율을 보장하는 것이 핵심이다. 예를 들어, 어떤 알고리즘이 항상 최적해의 2배 이하의 값을 출력한다면, 이 알고리즘은 2-근사 알고리즘이라고 한다.

근사 알고리즘은 문제의 특성에 따라 그 설계 방법과 가능한 근사 비율이 크게 달라진다. 일부 문제는 임의의 작은 오차를 허용하는 다항 시간 근사 체계(PTAS)를 가지는 반면, P-NP 문제가 P ≠ NP로 밝혀질 경우 근사조차 매우 어려운 문제들도 존재한다. 대표적인 NP-완전 문제들에 대한 근사 알고리즘의 성능은 다음과 같이 다양하다.

이러한 근사 기법은 조합 최적화, 운용 과학, 스케줄링 등 다양한 실용 분야에서 NP-완전 문제를 실질적으로 처리하는 데 필수적인 도구가 된다. 최적화 엔진이나 물류 시스템, 회로 설계 등에서 효율성과 해의 질 사이의 균형을 맞추기 위해 적극적으로 도입된다.

NP-완전 문제를 정확하게 해결하는 다항 시간 알고리즘이 발견되지 않은 상황에서, 실제 응용에서는 휴리스틱 알고리즘이 널리 사용된다. 휴리스틱 알고리즘은 문제의 최적해를 보장하지는 않지만, 합리적인 시간 내에 실용적으로 좋은 해를 찾아주는 방법이다. 이는 외판원 문제나 작업 스케줄링과 같이 실세계에서 빈번히 마주치는 NP-완전 문제를 처리할 때 특히 유용하다.

휴리스틱 알고리즘은 크게 구성적 휴리스틱과 개선적 휴리스틱으로 나눌 수 있다. 구성적 휴리스틱은 무에서 시작해 점차 해를 구축해 나가는 방식이며, 탐욕 알고리즘이 대표적이다. 개선적 휴리스틱은 이미 존재하는 초기 해를 점차 개선시키는 방식으로, 국소 탐색, 시뮬레이티드 어닐링, 탭 서치, 유전 알고리즘 등이 여기에 속한다. 이러한 방법들은 해의 공간을 효율적으로 탐색하여 지역 최적해에 빠지는 것을 피하거나 탈출하려는 전략을 사용한다.

이러한 휴리스틱 기법은 운용 연구, 인공지능, 생물정보학 등 다양한 분야에서 NP-완전 문제를 실용적으로 푸는 핵심 도구로 자리 잡았다. 완벽한 최적해 대신 시간과 해의 질 사이의 균형을 추구하며, 복잡한 현실 문제를 처리하는 데 필수적이다.

매개변수화 알고리즘은 NP-완전 문제를 해결하기 위한 접근법 중 하나로, 문제의 난이도를 입력 크기뿐만 아니라 문제의 구조를 나타내는 추가적인 매개변수에 의존하도록 설계한다. 이 방법은 고정 매개변수 난이도라는 개념을 기반으로 한다. 핵심 아이디어는 문제의 복잡성이 입력 크기 n에 대해서는 지수적으로 증가할 수 있지만, 특정 매개변수 k에 대해서만 의존하도록 제한하는 것이다. 예를 들어, 꼭짓점 커버 문제에서 목표 커버 크기 k를 매개변수로 삼으면, 알고리즘의 실행 시간이 O(f(k) * n^c) 형태가 되도록 설계할 수 있다. 여기서 f(k)는 k에만 의존하는 함수(예: 지수 함수)이고, n^c는 입력 크기에 대한 다항식 항이다.

이러한 알고리즘은 매개변수 k가 실제 상황에서 충분히 작을 때 유용하다. 많은 NP-완전 문제는 실제 인스턴스에서 특정 매개변수가 작은 값을 가지는 경우가 많기 때문이다. 예를 들어, 외판원 문제에서 방문해야 할 주요 도시의 수가 제한적이라면, 혹은 배낭 문제에서 선택해야 할 물품의 종류가 적다면, 매개변수화 알고리즘을 통해 실용적인 시간 내에 최적해를 구할 가능성이 높아진다. 이는 문제의 구조적 특성을 활용하여 문제를 더 쉽게 분해하거나 검색 공간을 효과적으로 줄이는 기법들을 사용한다.

매개변수화 알고리즘의 설계에는 다양한 기법이 동원된다. 커널화는 원래 문제 인스턴스를 매개변수 k에만 의존하는 크기의 동등한 작은 인스턴스로 변환하는 전처리 과정이다. 가지치기 검색은 재귀적 탐색 과정에서 매개변수를 기반으로 불필요한 분기를 일찍 잘라내는 방법이다. 동적 계획법도 특정 매개변수에 초점을 맞춰 상태 공간을 구성하는 방식으로 적용될 수 있다. 이러한 기법들은 이론적 연구뿐만 아니라 실제 조합 최적화 문제를 해결하는 소프트웨어에도 점차 적용되고 있다.