계산 복잡도 이론

점근 표기법은 알고리즘의 효율성을 입력 크기가 매우 커질 때의 행동으로 설명하는 수학적 도구이다. 이는 상수 계수나 낮은 차수의 항과 같은 상세한 사항을 무시하고, 성장률의 큰 그림에 집중할 수 있게 해준다. 가장 널리 사용되는 표기법은 빅 오(Big-O), 빅 세타(Θ), 빅 오메가(Ω)이다.

빅 오 표기법(O)은 알고리즘의 실행 시간 또는 사용 공간에 대한 상한(upper bound)을 나타낸다. 예를 들어, 어떤 알고리즘의 시간 복잡도가 O(n^2)이라면, 이 알고리즘의 수행 시간은 최악의 경우 입력 크기 n의 제곱에 비례하여 증가한다는 의미이다. 빅 오메가 표기법(Ω)은 반대로 하한(lower bound)을 나타낸다. Ω(n log n)은 알고리즘이 아무리 좋아도 최소한 n log n에 비례하는 시간은 필요하다는 것을 뜻한다. 빅 세타 표기법(Θ)은 상한과 하한이 동일한 경우, 즉 점근적으로 엄밀한 한계(tight bound)를 나타낼 때 사용한다. Θ(n^2)은 알고리즘이 최악과 최선의 경우 모두 n^2에 비례하는 속도로 성장함을 의미한다.

이러한 표기법은 알고리즘을 분류하고 비교하는 데 필수적이다. 예를 들어, 동일한 문제를 해결하는 알고리즘 A가 O(n log n)이고 알고리즘 B가 O(n^2)이라면, 충분히 큰 입력에 대해서는 일반적으로 알고리즘 A가 더 효율적이라고 판단할 수 있다. 점근 표기법은 시간 복잡도와 공간 복잡도를 논의할 때의 공통 언어 역할을 하며, 복잡도 종류를 정의하는 기초가 된다.

다항 시간(Polynomial time)은 알고리즘의 실행 시간이 입력 크기 n에 대한 다항식 함수(예: n, n^2, n^3)로 상한이 제한될 때를 말한다. 이는 현실적으로 '효율적으로 풀 수 있는' 문제의 기준으로 널리 받아들여진다. 예를 들어, 정렬이나 최단 경로 찾기와 같은 많은 기본적인 문제들은 다항 시간 알고리즘을 가진다.

반면, 지수 시간(Exponential time)은 실행 시간이 입력 크기에 대해 지수 함수(예: 2^n, n!)로 증가하는 경우를 말한다. 이러한 알고리즘은 입력 크기가 조금만 커져도 필요한 계산량이 폭발적으로 증가하여, 현실적인 시간 내에 문제를 해결하는 것이 사실상 불가능해진다.

이 구분은 계산 이론에서 문제의 난이도를 분류하는 핵심이다. 복잡도 종류 P는 결정 문제 중 다항 시간 내에 해결할 수 있는 문제들의 집합으로 정의된다. 이는 컴퓨터가 '빠르게' 답을 찾을 수 있는 문제들의 범주를 형성한다. 다항 시간의 개념은 문제 간의 난이도를 비교하는 '다항 시간 환원'의 기초가 되며, NP-완전 이론의 토대를 이룬다.

P와 NP는 계산 복잡도 이론에서 가장 잘 알려진 두 가지 복잡도 종류이다. 이들은 문제를 해결하는 데 필요한 계산 자원, 특히 시간의 양에 따라 분류한다.

P는 결정론적 튜링 기계로 다항 시간(polynomial time) 내에 풀 수 있는 결정 문제의 집합이다. 즉, 입력 크기 n에 대해 n의 다항식으로 표현되는 시간(예: O(n), O(n^2), O(n^3)) 안에 정답을 '찾을 수 있는' 문제들의 클래스이다. 정렬, 최단 경로 찾기, 최소 신장 트리 등 많은 실용적인 알고리즘이 여기에 속한다.

NP는 비결정론적 튜링 기계로 다항 시간 내에 풀 수 있는 결정 문제의 집합으로 정의된다. 더 직관적으로 설명하면, 어떤 문제의 주어진 '답안'(증명서)이 맞는지 여부를 다항 시간 내에 '확인할 수 있는' 문제들의 클래스이다. 예를 들어, 해밀턴 경로 문제에서 특정 경로가 모든 정점을 한 번씩만 방문하는지는 쉽게 확인할 수 있지만, 그러한 경로 자체를 처음부터 찾는 것은 어려울 수 있다. 모든 P 문제는 NP에도 속하지만(P ⊆ NP), 그 역이 성립하는지는 알려지지 않았으며, 이것이 바로 유명한 P-NP 문제의 핵심이다.

NP에 속하면서 동시에 NP 내의 다른 어떤 문제보다도 '어렵다'고 간주되는 문제들을 NP-완전 문제라고 한다. 만약 하나의 NP-완전 문제라도 P에 속한다는 것이 증명된다면, 모든 NP 문제가 P에 속하게 되어 P=NP가 성립하게 된다. 현재까지 수많은 연구에도 불구하고 이 문제는 미해결 상태로 남아 있으며, 클레이 수학연구소가 선정한 7대 밀레니엄 문제 중 하나이다.

NP-완전(NP-Complete)은 NP에 속하는 모든 문제를 다항 시간 내에 환원할 수 있는 문제들의 집합이다. 즉, NP-완전 문제 중 단 하나라도 다항 시간에 해결할 수 있는 알고리즘이 발견된다면, NP에 속하는 모든 문제가 다항 시간에 풀리게 되어 P=NP가 증명된다. 반대로, NP-완전 문제 중 하나가 다항 시간에 풀릴 수 없다면 P≠NP가 된다. 따라서 NP-완전 문제들은 P-NP 문제의 핵심 열쇠로 여겨진다.

NP-완전성을 증명하기 위해서는 두 단계가 필요하다. 첫째, 해당 문제가 NP에 속함을 보여야 한다. 이는 문제의 답안(예: 해밀턴 경로의 순서)이 주어졌을 때, 그 답안이 올바른지 다항 시간 내에 검증할 수 있어야 함을 의미한다. 둘째, 이미 알려진 NP-완전 문제를 다항 시간 내에 해당 문제로 환원할 수 있음을 보여야 한다. 이 환원 과정을 통해 새로운 문제가 적어도 기존 NP-완전 문제만큼 어렵다는 것을 입증한다.

대표적인 NP-완전 문제는 다음과 같다.

NP-완전 문제들은 실제로 빈번히 등장하며, 정확한 최적해를 다항 시간에 구하는 일반적인 방법은 알려져 있지 않다. 따라서 실제 응용에서는 근사 알고리즘, 휴리스틱, 또는 제한된 조건 하에서의 효율적인 알고리즘을 사용하여 접근한다.

NP-난해(NP-hard)는 NP에 속하는 모든 문제를 다항 시간 내에 환원할 수 있는 문제들의 집합을 가리킨다. NP-완전 문제는 NP-난해이면서 동시에 NP에 속하지만, NP-난해 문제는 반드시 NP에 속할 필요는 없다. 즉, NP-난해는 NP-완전을 포함하는 더 넓은 개념이다.

NP-난해 문제는 NP에 속하는 문제들보다 계산적으로 더 어려울 수 있다. 예를 들어, 정지 문제와 같은 결정 불가능한 문제도 NP-난해로 분류될 수 있다. 이는 NP-난해의 정의가 문제의 난이도 하한을 나타내기 때문이다. NP-난해 문제 중 하나라도 다항 시간에 풀린다면, NP에 속하는 모든 문제가 다항 시간에 풀리게 되어 P=NP가 성립한다.

NP-난해 문제는 실제로 최적해를 구하는 최적화 문제에서 자주 등장한다. 예를 들어, 외판원 문제의 결정 문제 버전은 NP-완전이지만, 최단 경로를 찾는 최적화 버전은 일반적으로 NP-난해로 간주된다. 이러한 문제들은 정확한 해를 구하는 데 엄청난 시간이 소요되므로, 근사 알고리즘 또는 휴리스틱 방법을 통해 실용적으로 접근하는 경우가 많다.

PSPACE는 결정론적 튜링 기계가 다항 공간(메모리)을 사용하여 풀 수 있는 결정 문제들의 집합이다. 즉, 문제를 해결하는 데 필요한 메모리 공간의 양이 입력 크기의 다항 함수로 제한된다. 시간 제한은 명시적으로 두지 않는다. 모든 NP 문제는 PSPACE에 포함된다고 알려져 있으며, P ⊆ NP ⊆ PSPACE 관계가 성립한다. PSPACE-완전 문제의 예로는 양자화된 불린 식(QBF) 평가나 특정 게임의 최적 전략 존재 여부 판정 등이 있다.

EXPTIME은 결정론적 튜링 기계가 지수 시간(2^(다항식)) 안에 풀 수 있는 결정 문제들의 집합이다. 즉, 최악의 경우 실행 시간이 입력 크기에 대한 지수 함수로 제한된다. PSPACE ⊆ EXPTIME 관계가 성립한다. EXPTIME-완전 문제에는 보편적 튜링 기계가 주어진 지수 시간 한계 내에 정지하는지 판정하는 문제 등이 포함된다.

이 외에도 복잡도 종류는 다양하게 정의된다. 예를 들어, NPSPACE는 비결정론적 튜링 기계가 다항 공간을 사용하여 풀 수 있는 문제들의 집합인데, 사비치 정리에 의해 PSPACE와 동일하다는 것이 증명되었다. 또 다른 중요한 종류로는 다항 시간 내에 확률적 알고리즘으로 풀 수 있는 문제들의 집합인 BPP가 있으며, P와의 관계는 아직 완전히 밝혀지지 않았다.

아래 표는 주요 복잡도 종류와 그 관계를 요약한 것이다.

이러한 복잡도 종류들은 계산이 가능한 문제들을 자원(시간, 공간)의 사용량에 따라 분류하며, 서로 간의 포함 관계가 연구의 주요 주제 중 하나이다. 특히 P-NP 문제는 이러한 위계 속에서 가장 유명한 미해결 문제이다.

다항 시간 환원은 한 계산 문제를 다른 문제로 변환하는 방법이다. 이 변환 과정 자체는 다항 시간 내에 수행되어야 한다. 만약 문제 A를 문제 B로 다항 시간 환원할 수 있고, 문제 B를 푸는 효율적인 알고리즘이 존재한다면, 그 알고리즘을 이용해 문제 A도 효율적으로 해결할 수 있다. 이는 문제 간의 상대적 난이도를 비교하는 핵심 도구이다.

주로 복잡도 종류, 특히 NP-완전 문제를 연구할 때 사용된다. 어떤 문제가 NP-완전임을 증명하기 위해서는, 이미 알려진 NP-완전 문제를 해당 문제로 다항 시간 환원할 수 있음을 보이면 된다. 이는 환원의 방향이 중요함을 의미한다. 즉, 어려운 문제(예: NP-완전 문제)를 새로운 문제로 환원함으로써, 새로운 문제가 적어도 그만큼은 어렵다는 것을 입증하는 것이다.

다항 시간 환원의 주요 유형은 다음과 같다.

이러한 환원 개념을 통해 수많은 문제들이 NP-완전 문제 클래스로 묶일 수 있었다. 예를 들어, 충족 가능성 문제(SAT)는 최초로 증명된 NP-완전 문제이며, 다른 NP-완전 문제들은 SAT로부터의 다항 시간 환원을 통해 그 난이도를 입증한다. 따라서 다항 시간 환원은 계산 난해성 이론의 근간을 이루며, P-NP 문제를 이해하는 데 필수적이다.

쿡-레빈 정리는 계산 복잡도 이론의 근간을 이루는 중요한 정리이다. 이 정리는 특정한 문제가 다른 모든 NP 문제의 '대표자' 역할을 할 수 있음을 최초로 증명했다. 스티븐 쿡과 레오니드 레빈이 각각 독립적으로 제시한 이 결과는 NP-완전이라는 개념을 정의하는 데 결정적인 기여를 했다.

이 정리의 핵심은 만약 한 문제가 NP-완전하다면, 그 문제를 다항 시간 내에 해결할 수 있는 알고리즘이 존재한다는 것은 곧 NP에 속하는 모든 문제를 다항 시간에 해결할 수 있음을 의미한다는 것이다. 쿡과 레빈은 논리학의 만족 가능성 문제(SAT)가 바로 그러한 성질을 가진 최초의 문제임을 보였다. 즉, SAT 문제는 NP에 속하면서, NP에 속하는 임의의 다른 문제를 다항 시간 안에 SAT 문제로 변환(환원)할 수 있다.

이 정리의 증명은 비결정적 튜링 기계가 다항 시간 안에 답을 낼 수 있는 모든 문제의 계산 과정을, 크기가 다항식으로 제한되는 논리 명제(부울 식)로 정확히 묘사(인코딩)할 수 있음을 보이는 방식으로 이루어진다. 따라서 쿡-레빈 정리는 계산 이론과 논리학을 연결하는 강력한 다리 역할을 한다. 이후 수많은 문제들이 SAT 문제로 환원됨으로써 NP-완전임이 증명되었으며, 이는 복잡도 이론에서 문제의 난이도를 분류하는 강력한 도구가 되었다.

P-NP 문제는 계산 복잡도 이론에서 가장 유명하고 중요한 미해결 문제이다. 이 문제는 "P 집합에 속한 문제들과 NP 집합에 속한 문제들이 실제로 같은가?"라는 질문으로 요약된다. 다시 말해, 다항 시간 내에 답을 검증할 수 있는 모든 문제(NP)가 다항 시간 내에 직접 해결될 수도 있는가(P)를 묻는 것이다. 만약 P와 NP가 같다면, 현재 매우 어렵다고 여겨지는 많은 문제들이 사실은 효율적으로 해결할 수 있는 알고리즘이 존재한다는 의미가 된다.

이 문제의 중요성은 그 해답이 수학, 암호학, 인공지능, 운영 연구 등 다양한 분야에 지대한 영향을 미칠 것이기 때문이다. 예를 들어, 현대 암호 체계의 많은 부분은 특정 문제들이 실제로 풀기 어렵다는 가정에 의존하고 있다. 만약 P=NP가 증명된다면, 이러한 암호 체계는 근본적으로 재평가되어야 할 것이다. 반대로, P≠NP가 증명되면, 우리가 현재 어렵다고 믿는 많은 문제들은 본질적으로 효율적인 해법을 가질 수 없게 되어, 계산의 한계에 대한 확신을 얻게 된다.

P-NP 문제는 1971년 스티븐 쿡과 레오니드 레빈에 의해 공식적으로 제기되었으며, 클레이 수학연구소가 선정한 7대 밀레니엄 문제 중 하나이다. 이 문제를 해결하는 데는 여러 접근법이 시도되어 왔지만, 결정적인 진전은 아직 이루어지지 않았다. 대부분의 학자들은 직관과 부분적인 증거를 바탕으로 P와 NP는 다를 것이라고 믿고 있으나, 이는 엄밀한 수학적 증명으로 확인된 바 없다.

이 문제의 해결은 단순한 호기심을 넘어, 계산 가능성의 본질과 한계를 이해하는 데 핵심적인 역할을 할 것이다. 따라서 이론 컴퓨터 과학의 궁극적인 목표 중 하나로 남아 있다.