NP (복잡도)

NP의 정의를 이해하는 핵심은 비결정론적 튜링 기계라는 계산 모델이다. 이는 기존의 결정론적 튜링 기계와 달리, 계산의 각 단계에서 여러 가지 가능한 다음 행동 중 하나를 '추측'하여 선택할 수 있는 이론적 기계이다. 어떤 문제의 답이 '예'일 때, 비결정론적 튜링 기계는 운좋게 올바른 추측 경로를 따라 다항 시간 안에 그 사실을 확인하고 멈출 수 있다. NP는 바로 이렇게 비결정론적 튜링 기계로 다항 시간 안에 답이 '예'임을 판정할 수 있는 모든 판정 문제의 집합으로 정의된다.

이 개념은 '검증'의 관점에서도 설명된다. 어떤 문제가 NP에 속한다는 것은, 문제의 예시 인스턴스와 함께 그에 대한 '증거'가 주어졌을 때, 그 증거가 맞는지 틀린지를 결정론적 튜링 기계로 다항 시간 안에 확인할 수 있다는 뜻이다. 예를 들어, 외판원 문제에서 특정 경로가 주어지면 그 경로의 총 길이가 기준치 이하인지는 쉽게 계산해 확인할 수 있다. 이때 주어진 경로가 바로 증거 역할을 한다.

따라서 NP는 '다항 시간 안에 답을 추측하여 확인할 수 있는 문제들의 클래스'로 요약할 수 있다. 이 정의는 문제를 해결하는 데 걸리는 시간보다는 해답을 검증하는 데 걸리는 시간에 초점을 맞추며, 이는 P와의 근본적인 차이점이 된다. P는 결정론적 기계로 다항 시간 안에 해답 자체를 찾을 수 있는 문제들의 집합이다.

NP에 속하는 문제는 비결정론적 튜링 기계로 다항 시간 안에 답을 '찾을' 수 있는 문제로 정의되지만, 이는 직관적으로 이해하기 어려울 수 있다. 이를 보다 쉽게 이해할 수 있는 동등한 정의가 바로 검증자를 이용한 접근이다. 어떤 문제가 NP에 속한다는 것은, 그 문제의 '예'라고 주어진 답안(증명서)이 올바른지 여부를 결정론적 튜링 기계를 사용하여 다항 시간 안에 *검증*할 수 있다는 뜻이다.

예를 들어, 외판원 문제의 경우, "이 경로의 총 길이가 K 이하인가?"라는 질문에 대해, 어떤 특정 경로를 답안으로 제시하면, 우리는 그 경로가 모든 도시를 정확히 한 번씩 방문하는지, 그리고 총 거리를 계산해 K 이하인지 쉽게 확인할 수 있다. 이때 경로를 찾는 것은 매우 어려울 수 있지만, 주어진 경로가 조건을 만족하는지 *검증*하는 것은 비교적 쉽다. 이렇게 주어진 답안의 정당성을 빠르게 확인할 수 있는 알고리즘을 검증자라고 부른다.

따라서 NP는 다항 시간 검증 가능한 문제들의 집합으로도 특징지을 수 있다. 이 관점은 P-NP 문제를 이해하는 데 중요한데, P는 답을 *찾는* 데 다항 시간이 걸리는 문제들의 집합인 반면, NP는 답을 *검증하는* 데 다항 시간이 걸리는 문제들의 집합이다. 어떤 문제의 답을 찾는 것보다 검증하는 것이 당연히 쉬울 것이므로, P가 NP의 부분집합이라는 관계(P ⊆ NP)는 이 관점에서 자연스럽게 받아들여진다.

다항식 시간 환산은 한 문제를 다른 문제로 변환하는 방법이다. 이 변환 과정 자체가 다항식 시간 내에 이루어져야 하며, 변환된 문제의 답이 원래 문제의 답과 동일해야 한다. 즉, 문제 A를 문제 B로 환산할 수 있다면, 문제 B를 푸는 알고리즘이 존재할 경우 그 알고리즘을 이용해 문제 A도 풀 수 있게 된다.

이 환산 개념은 NP-완전 문제를 정의하는 데 핵심적인 역할을 한다. 어떤 문제가 NP-완전임을 증명하기 위해서는, 먼저 그 문제가 NP에 속함을 보이고, 이미 알려진 NP-완전 문제를 다항식 시간 내에 해당 문제로 환산할 수 있음을 보여야 한다. 이러한 환산 가능성은 문제들의 계산적 난이도를 비교하는 강력한 도구가 된다.

예를 들어, 만족성 문제(SAT)는 최초로 증명된 NP-완전 문제이다. 이후 해밀턴 경로 문제나 그래프 색칠 문제 등이 NP-완전임을 증명할 때는, SAT 문제를 각각의 문제로 다항식 시간 환산하는 방법을 구성함으로써 이루어진다. 이는 SAT가 NP 내의 모든 문제를 대표하는 '표준' 난제임을 의미한다.

다항식 시간 환산은 문제들의 상대적 난이도를 계층화하는 데 사용된다. 문제 A가 문제 B로 환산 가능하다는 것은, 문제 B가 문제 A 이상으로 어렵거나 최소한 같게 어렵다는 것을 의미한다. 따라서 NP-완전 문제들은 서로 동등한 난이도를 가지며, 이들 중 하나라도 다항식 시간에 풀리는 알고리즘이 발견된다면 NP에 속한 모든 문제가 쉽게 풀리게 된다.

NP-완전 문제는 NP (복잡도)에 속하는 모든 문제를 다항 시간 내에 환원할 수 있는, NP 내에서 가장 어려운 문제들의 집합을 가리킨다. 이 문제들 중 하나라도 다항 시간에 해결하는 효율적인 알고리즘이 발견된다면, 모든 NP 문제가 다항 시간에 풀리게 되어 P=NP가 증명된다. 반대로, 이들 중 하나라도 다항 시간에 풀 수 없다는 것이 증명되면 P≠NP가 된다.

대표적인 NP-완전 문제들은 다양한 분야에서 발견되며, 그 중 가장 유명한 것은 만족성 문제(SAT)이다. 이는 쿡-레빈 정리에 의해 최초로 NP-완전임이 증명된 문제로, 주어진 불린 회로나 명제 논리식이 참이 되도록 변수에 값을 할당할 수 있는지 판정하는 문제이다. SAT는 논리학과 전자 설계 자동화 등에서 중요한 기초 문제로 활용된다.

그 외에도 조합 최적화와 그래프 이론 분야에서 여러 중요한 NP-완전 문제들이 알려져 있다. 다음은 그 대표적인 예시들이다.

이들 문제는 운영 연구, 물류, 일정 계획, 회로 설계 등 실생활의 다양한 최적화 문제와 밀접하게 연결되어 있어, 이론적 중요성뿐만 아니라 실용적 의미도 매우 크다.

쿡-레빈 정리는 계산 복잡도 이론의 핵심적인 정리로, 만족성 문제(SAT)가 NP-완전이라는 것을 증명한다. 이 정리는 스티븐 쿡과 레오니드 레빈이 각각 독립적으로 제시했으며, NP-완전이라는 개념을 최초로 정의하고 그 첫 번째 예시를 제시했다는 점에서 역사적 의의가 크다.

이 정리의 핵심은 모든 NP 문제를 다항식 시간 환산을 통해 만족성 문제로 변환할 수 있다는 것이다. 즉, 만족성 문제를 다항 시간 안에 해결할 수 있는 알고리즘이 존재한다면, 그 알고리즘을 이용해 모든 NP 문제를 다항 시간 안에 해결할 수 있게 된다. 반대로, 만족성 문제가 다항 시간 안에 풀리지 않는다면, NP-완전으로 분류된 다른 모든 문제들도 다항 시간 안에 풀 수 없음을 의미한다.

쿡-레빈 정리는 NP-완전 문제들의 존재를 처음으로 보였을 뿐만 아니라, 이후 수많은 다른 문제들(예: 외판원 문제, 해밀턴 경로 문제, 그래프 색칠 문제 등)이 만족성 문제로 환원 가능함을 증명함으로써 그들 역시 NP-완전임을 입증하는 방법론적 토대를 제공했다. 이는 P-NP 문제를 이해하는 데 있어 결정적인 역할을 한다.

P는 결정론적 튜링 기계로 다항 시간 안에 해결할 수 있는 판정 문제들의 집합이다. 이는 쉽게 말해, 주어진 문제의 답을 컴퓨터가 비교적 빠른 시간 내에 정확하게 찾아낼 수 있는 문제들의 범주를 의미한다. P에 속하는 문제들은 효율적으로 해결 가능한 문제로 여겨지며, 정렬이나 최단 경로 문제와 같은 많은 기본적인 알고리즘 문제들이 이에 포함된다.

P와 NP의 관계는 계산 복잡도 이론의 핵심적인 질문 중 하나이다. 현재 학계에서는 P가 NP의 진부분집합일 것이라고 추측하지만(P ⊂ NP), 이는 아직 증명되지 않았다. 만약 P = NP가 증명된다면, 현재 어렵다고 알려진 많은 문제들도 효율적으로 해결할 수 있게 되어 암호학과 최적화 분야에 지대한 영향을 미칠 것이다.

P에 속하는 대표적인 문제들은 다음과 같다.

이러한 문제들은 다항 시간 알고리즘이 존재하여, 입력 크기가 커져도 실용적인 시간 내에 해를 구할 수 있다는 특징을 가진다. 따라서 P는 계산 이론에서 '풀기 쉬운' 문제들의 집합으로 정의된다.

co-NP는 계산 복잡도 이론에서 중요한 복잡도 종류 중 하나이다. 이는 어떤 문제의 '보수 문제'가 NP에 속하는 문제들의 집합으로 정의된다. 즉, 주어진 문제의 답이 '아니오'일 때, 그 '아니오' 답을 다항 시간 안에 확인할 수 있는 증거가 존재하는 문제들이 co-NP에 속한다.

예를 들어, 명제 논리식이 모든 경우에 참인지(즉, 항진식인지) 판별하는 문제는 co-NP에 속하는 대표적인 문제이다. 이 문제의 보수 문제는 "주어진 논리식이 거짓이 되는 경우가 존재하는가?" 즉, 만족성 문제(SAT)인데, SAT는 NP-완전 문제로 알려져 있다. 따라서 항진식 판별 문제는 co-NP-완전 문제로 여겨진다.

P, NP, co-NP 사이의 관계는 아직 명확히 밝혀지지 않았다. P는 NP와 co-NP의 교집합에 포함되는 것으로 알려져 있다. 만약 P-NP 문제에서 P = NP가 증명된다면, NP = co-NP가 성립하게 된다. 그러나 NP = co-NP가 반드시 P = NP를 의미하는 것은 아니며, 이는 여전히 열려 있는 질문이다.

PSPACE는 계산 복잡도 이론에서 사용되는 중요한 복잡도 종류 중 하나이다. PSPACE는 결정론적 또는 비결정론적 튜링 기계가 다항 공간(메모리)만을 사용하여 풀 수 있는 모든 판정 문제들의 집합으로 정의된다. 여기서 공간이란 계산 과정에서 사용되는 메모리 또는 작업 공간의 크기를 의미하며, 시간 제약보다는 공간 제약에 초점을 맞춘다.

PSPACE와 다른 복잡도 종류와의 관계는 잘 알려져 있다. 모든 다항 시간 내에 풀리는 문제들의 집합인 P는 PSPACE에 포함되며, NP 또한 PSPACE에 포함된다. 이는 다항 시간 안에 풀리거나 검증될 수 있는 문제는 당연히 다항 공간 안에서도 해결될 수 있기 때문이다. 더 나아가, EXPTIME과의 관계에서 PSPACE는 EXPTIME에 포함되는 것으로 알려져 있다. 이러한 포함 관계는 P ⊆ NP ⊆ PSPACE ⊆ EXPTIME으로 요약할 수 있다.

PSPACE에 속하는 대표적인 문제로는 양자화된 불 논리나 특정 형태의 게임 이론 문제들이 있다. 또한, PSPACE-완전이라는 개념이 존재하는데, 이는 PSPACE 내에서 가장 어려운 문제들의 집합을 의미한다. 모든 PSPACE 문제를 다항 공간 안에서 환원할 수 있는 문제가 PSPACE-완전 문제이다. 이러한 문제들은 NP-완전 문제와 마찬가지로 계산적으로 매우 어려운 것으로 간주된다.

PSPACE의 연구는 알고리즘 설계와 계산 가능성의 한계를 이해하는 데 중요한 역할을 한다. 특히 시간 복잡도와 공간 복잡도가 어떻게 서로 다른 계산 난이도를 정의하는지 보여주는 핵심 사례이다. P 대 NP 문제와 유사하게, P 대 PSPACE 문제 역시 중요한 미해결 문제로 남아 있으며, 이는 다항 시간과 다항 공간의 능력이 실제로 동일한지에 대한 질문을 던진다.

EXPTIME은 계산 복잡도 이론에서 결정론적 튜링 기계로 최악의 경우 지수 시간(O(2^p(n))) 안에 풀 수 있는 모든 판정 문제의 집합을 나타내는 복잡도 종류이다. 여기서 p(n)은 입력 크기 n에 대한 다항식 함수를 의미한다. 이는 다항식 시간 안에 풀 수 있는 문제들의 집합인 P와는 구별되며, P는 EXPTIME의 진부분집합(P ⊊ EXPTIME)으로 알려져 있다.

EXPTIME에는 체스나 장기 같은 특정 형태의 완전 정보 보드 게임의 최적 수를 찾는 문제와 같이 실용적으로 매우 어려운 문제들이 포함된다. 또한, 시간 계층 정리에 의해 P와 EXPTIME은 서로 다르며, EXPTIME에는 P에는 속하지 않는 문제들이 반드시 존재함이 증명되어 있다. 이는 다항식 시간보다 지수 시간이 본질적으로 더 많은 계산 능력을 필요로 함을 의미한다.

EXPTIME과 NP의 관계는 NP ⊆ EXPTIME이다. 모든 NP 문제는 비결정론적 튜링 기계로 다항 시간 안에 판정 가능하며, 이를 결정론적 튜링 기계로 시뮬레이션하면 지수 시간이 소요될 수 있기 때문이다. 그러나 NP가 EXPTIME의 진부분집합인지, 혹은 같은 집합인지는 아직 알려지지 않았으며, 이는 P-NP 문제보다 더 넓은 미해결 문제의 일부이다.

이러한 복잡도 종류들의 계층 구조는 계산 가능한 문제들의 난이도를 이해하는 데 중요한 틀을 제공한다.