복잡도 종류

점근적 표기법은 알고리즘의 효율성을 분석할 때, 입력 크기가 충분히 커질 때의 성장률에 초점을 맞추는 수학적 도구이다. 이는 상수 계수나 낮은 차수의 항과 같은 상세한 부분을 무시하고, 알고리즘이 소요하는 시간이나 공간의 증가 추세를 파악하는 데 핵심적이다. 가장 널리 사용되는 표기법은 빅 오 표기법(Big-O notation)으로, 알고리즘의 수행 시간에 대한 상한(최악의 경우)을 나타낸다.

주요 점근적 표기법에는 빅 오 외에도 빅 세타 표기법(Big-Θ notation)과 빅 오메가 표기법(Big-Ω notation)이 있다. 빅 세타 표기법은 점근적으로 상한과 하한이 동일한 경우, 즉 정확한 성장률을 나타낼 때 사용한다. 빅 오메가 표기법은 알고리즘 수행 시간의 하한(최선의 경우 또는 적어도 필요한 자원)을 표현한다. 이 세 가지 표기법은 알고리즘의 시간 복잡도와 공간 복잡도를 논할 때 공통적으로 적용된다.

점근적 분석의 실제 활용은 다음과 같은 표로 정리할 수 있다.

이러한 표기법을 통해 알고리즘을 O(n²), Θ(n log n), Ω(n)과 같이 분류함으로써, 서로 다른 알고리즘의 효율성을 이론적으로 비교하고 계산 복잡도 이론에서 복잡도 종류를 정의하는 기초를 마련한다.

시간 복잡도는 입력 크기에 대한 알고리즘의 실행 시간 증가율을 나타낸다. 점근적 표기법을 사용하여 분류하며, 대표적인 시간 복잡도 클래스로는 상수 시간, 로그 시간, 선형 시간, 다항 시간, 지수 시간 등이 있다. 이들은 문제의 난이도와 계산 가능성을 이해하는 기본 틀을 제공한다.

가장 이상적인 복잡도는 입력 크기와 무관하게 항상 일정한 시간이 소요되는 상수 시간 복잡도(O(1))이다. 데이터의 개수에 비례하여 시간이 증가하는 선형 시간 복잡도(O(n))와, 데이터가 두 배로 늘어날 때 한 단계의 연산만 추가로 필요한 로그 시간 복잡도(O(log n))도 효율적인 알고리즘의 대표적인 예시이다. 이들보다는 느리지만, 입력 크기의 거듭제곱에 비례하는 다항 시간 복잡도(O(n^k))는 현실적으로 '풀기 쉬운' 문제들의 클래스인 P를 정의하는 기준이 된다.

반면, 특정 문제들은 다항 시간보다 훨씬 빠르게 증가하는 복잡도를 가진다. 대표적으로 지수 시간 복잡도(O(2^n))나 계승 시간 복잡도(O(n!))가 있으며, 이러한 복잡도를 가진 알고리즘은 입력 크기가 조금만 커져도 실행이 사실상 불가능해진다. NP-완전 문제들은 현재 알려진 최선의 알고리즘이 지수 시간 복잡도를 가지는 경우가 많아, 난해한 문제로 분류된다. 점근 표기법을 통해 이러한 복잡도 클래스들을 정량적으로 비교하고 분석할 수 있다.

P는 결정론적 튜링 기계에서 다항식 시간 안에 해결 가능한 결정 문제의 집합이다. 즉, 문제의 크기 n에 대해 최악의 경우에도 n의 다항식 함수로 표현되는 시간(예: O(n), O(n^2), O(n^3)) 안에 정확한 답(예/아니오)을 내놓을 수 있는 알고리즘이 존재하는 문제들을 포함한다. 이 클래스에는 정렬, 최단 경로 찾기, 최소 신장 트리 등 실용적으로 효율적으로 해결 가능한 많은 문제들이 속한다.

NP는 비결정론적 튜링 기계를 이용해 다항식 시간 안에 해결 가능한 결정 문제의 집합으로 정의된다. 좀 더 직관적으로 설명하면, 어떤 문제의 주어진 '후보 해답'이 맞는지 아닌지를 다항식 시간 안에 확인(검증)할 수 있다면 그 문제는 NP에 속한다. 예를 들어, 외판원 문제의 특정 경로가 주어진 길이 이하인지는 쉽게 확인할 수 있지만, 그런 경로를 처음부터 찾는 것은 어려울 수 있다.

P와 NP의 관계는 계산 복잡도 이론의 가장 중요한 미해결 문제이다. P가 NP의 부분집합이라는 것은 자명하지만, P가 NP와 진짜로 같은지(P=NP), 아니면 엄격한 부분집합인지(P≠NP)는 아직 증명되지 않았다. 만약 P=NP가 증명된다면, 현재 어렵다고 알려진 많은 문제들도 효율적으로 해결할 수 있는 알고리즘이 존재한다는 의미가 되어 컴퓨터 과학과 수학, 그리고 실생활에 엄청난 영향을 미칠 것이다. 그러나 대부분의 학자들은 P≠NP일 것이라고 추측하고 있다.

NP-완전은 NP에 속하는 모든 문제가 다항식 시간 내에 환산될 수 있는 문제들의 집합을 가리킨다. 다시 말해, NP-완전 문제 중 하나라도 다항식 시간에 해결할 수 있는 알고리즘이 발견된다면, NP에 속하는 모든 문제를 다항식 시간에 해결할 수 있게 되어 P와 NP가 같아지게 된다. 이는 계산 복잡도 이론의 가장 중요한 미해결 문제인 P-NP 문제의 핵심에 있다.

NP-완전성을 증명하기 위해서는 두 단계가 필요하다. 첫째, 해당 문제가 NP에 속함을 보여야 한다. 둘째, 이미 NP-완전임이 알려진 다른 문제를 다항식 시간 내에 이 문제로 환산할 수 있음을 보여야 한다. 최초의 NP-완전 문제는 스티븐 쿡이 1971년 증명한 충족 가능성 문제이다. 이후 수많은 문제들이 SAT 문제로부터의 환산을 통해 NP-완전임이 증명되었다.

NP-완전 문제의 대표적인 예로는 다음과 같은 것들이 있다.

이러한 문제들은 실세계에서 빈번히 등장하지만, 현재까지 알려진 가장 효율적인 알고리즘들도 최악의 경우 지수 시간 또는 그 이상의 복잡도를 가진다. 따라서 대규모 입력에 대해서는 근사 알고리즘이나 휴리스틱 방법을 사용하여 실용적인 해결책을 찾는 경우가 많다. NP-완전 문제의 존재는 알고리즘 설계에서 문제의 본질적 어려움을 이해하고 적절한 접근법을 선택하는 데 중요한 기준을 제공한다.

NP-난해는 NP에 속하는 모든 문제가 다항식 시간 내에 자신으로 환산될 수 있는 문제들의 집합을 가리킨다. 다시 말해, NP-난해 문제는 NP에 속한 어떤 문제보다도 해결하기 어렵거나 최소한 그만큼 어려운 문제이다. NP-난해 문제 중 하나라도 다항식 시간 내에 해결할 수 있는 알고리즘이 발견된다면, NP에 속하는 모든 문제가 다항식 시간에 풀리게 되어 P=NP가 증명되는 결과를 초래한다.

NP-난해 문제는 반드시 NP에 속할 필요는 없다는 점에서 NP-완전 문제와 구별된다. NP-완전 문제는 NP-난해 문제이면서 동시에 NP에 속하는 문제들의 집합이다. 따라서 NP-난해 문제의 범위가 더 넓으며, NP-완전 문제를 포함한다. NP에 속하지 않는 난해한 문제의 대표적인 예로는 정지 문제와 같은 계산 가능성 이론의 문제들이 있다.

NP-난해 문제는 이론적으로 매우 중요할 뿐만 아니라, 실제 조합 최적화 문제에서도 빈번하게 등장한다. 예를 들어, 외판원 문제의 결정 문제 버전은 NP-완전이지만, 최단 경로를 찾는 최적화 버전은 일반적으로 NP-난해로 분류된다. 이러한 문제들은 정확한 해를 구하는 데 필요한 시간이 문제 크기에 대해 지수적으로 증가하기 때문에, 대규모 실세계 문제에서는 근사 알고리즘이나 휴리스틱 방법을 통해 실용적인 해결책을 모색한다.

PSPACE는 결정론적 튜링 기계가 다항식 크기의 메모리 공간을 사용하여 해결할 수 있는 모든 결정 문제의 집합으로 정의된다. 여기서 공간이란 작업 공간(워킹 메모리)을 의미하며, 입력 자체를 저장하는 데 필요한 공간은 일반적으로 제외하거나 별도로 고려한다. 이는 시간 복잡도의 주요 클래스인 P나 NP가 시간 자원에 초점을 맞추는 것과 대비되어, 공간 자원의 효율성을 기준으로 문제를 분류한다.

PSPACE에 속하는 대표적인 문제로는 양자화된 불 논리(QBF) 판정 문제, 지리 게임(Geography game), 그리고 특정 보드 게임(예: 체스, 오목, 장기)의 최적 수를 판단하는 일반화된 문제들이 있다. 이들 문제는 해결하는 데 필요한 시간은 매우 길 수 있지만, 특정 알고리즘을 사용하면 비교적 적은 양의 메모리 공간 안에서 해결 과정을 진행할 수 있다는 특징을 가진다.

복잡도 클래스 간의 관계에서 PSPACE는 다음과 같은 포함 관계를 가진다. P ⊆ NP ⊆ PSPACE ⊆ EXPTIME이 성립하는 것으로 알려져 있다. 특히, P ≠ EXPTIME이 증명되었기 때문에, 이 포함 관계의 연결 고리 중 적어도 하나는 진부분집합 관계일 것이라고 추론할 수 있다. 그러나 P = PSPACE인지, 혹은 NP = PSPACE인지와 같은 구체적인 관계는 아직 해결되지 않은 난제로 남아 있다.

이 클래스는 공간 복잡도 이론의 핵심이며, 다항식 계층(Polynomial Hierarchy, PH)과도 깊은 연관이 있다. PSPACE-완전 문제는 PSPACE 내에서 가장 어려운 문제들의 집합으로, 이들 중 하나를 다항식 시간에 해결할 수 있다면 PSPACE 전체가 P에 포함된다는 것을 의미하게 되어, P = PSPACE가 증명되는 결과를 낳는다.

EXP는 EXPTIME의 약자로, 결정론적 튜링 기계를 사용하여 다항식 공간이 아닌 지수 시간 내에 해결할 수 있는 결정 문제들의 집합을 의미한다. 좀 더 정확히는, 입력 크기 n에 대해 최대 O(2^p(n)) 시간이 소요되는 알고리즘으로 해결 가능한 문제들의 복잡도 종류이다. 여기서 p(n)은 n에 대한 다항식 함수를 나타낸다.

이 클래스에는 매우 어려운 문제들이 포함되어 있으며, P나 NP에 속하는 많은 문제들과는 근본적으로 다른 차원의 계산 자원을 요구한다고 볼 수 있다. 예를 들어, 체스나 장기 같은 완전 정보 게임의 최적 수를 찾는 문제, 특정한 형식 논리 체계에서 주어진 명제가 참인지 확인하는 문제 등이 EXPTIME에 속하는 것으로 알려져 있다.

계산 복잡도 이론에서 EXP는 다음과 같은 포함 관계를 가진다. P ⊆ NP ⊆ PSPACE ⊆ EXP이다. 특히, P ≠ EXP임이 이미 증명되어 있어, 지수 시간이 필요한 문제들은 어떤 경우에도 다항식 시간 알고리즘으로 해결할 수 없음을 보여준다. 이는 시간 계층 정리에 의해 설명된다.

EXP와 유사하지만 구분되는 개념으로 NEXP가 있다. NEXP는 비결정론적 튜링 기계가 지수 시간 내에 해결할 수 있는 문제들의 클래스이다. P 대 NP 관계와 유사하게, EXP 대 NEXP 관계 역시 중요한 미해결 문제로 남아 있다.