계산 복잡도 이론

분야	[[이론 컴퓨터 과학]], [[수학]]
주요 문제	[[P-NP 문제]]
창시 시기	1960년대
주요 창시자	[[주라이 하트마니스]], [[리처드 스턴스]], [[앨런 코밤]]
상위 분야	[[계산 이론]]
관련 분야	[[알고리즘]], [[암호학]], [[정보 이론]]
핵심 개념	[[복잡도 클래스]], [[환원]], [[완전성]]
미해결 문제 수	다수 (P vs NP 등)
밀레니엄 문제	P ≠ NP 추측 (100만 달러 현상금)

'''계산 복잡도 이론'''(計算複雜度理論, {{lang|en|Computational Complexity Theory}})은 [[이론 컴퓨터 과학]]과 [[수학]]의 한 분야로, 계산 문제를 푸는 데 필요한 자원의 양에 따라 문제를 분류하고 그 본질적 난이도를 연구하는 학문이다. 여기서 자원이란 주로 '''시간'''(연산 단계 수)과 '''공간'''(메모리 사용량)을 의미하지만, [[통신 복잡도]], [[회로 복잡도]], [[난수]] 사용량 등 다양한 자원이 고려되기도 한다. 계산 복잡도 이론은 "어떤 문제가 본질적으로 얼마나 어려운가?"라는 근본적 질문에 답하려는 시도이며, 이는 [[알고리즘]] 설계, [[암호학]], [[인공지능]], [[최적화]] 등 컴퓨터 과학 전반에 깊은 영향을 미치고 있다. == 개요 == 계산 복잡도 이론의 핵심 목표는 계산 문제들을 그 '''본질적 난이도'''에 따라 체계적으로 분류하는 것이다. 이때 특정 알고리즘의 효율성을 분석하는 [[알고리즘 분석]]과는 구별되는데, 복잡도 이론은 특정 알고리즘이 아니라 문제 자체의 난이도에 관심을 갖는다. 즉, 어떤 문제를 풀 수 있는 '''가장 효율적인''' 알고리즘이 얼마나 많은 자원을 필요로 하는지를 연구한다. 이 분야에서 가장 기본적인 도구는 '''[[복잡도 클래스]]'''의 개념이다. 복잡도 클래스는 비슷한 양의 자원으로 풀 수 있는 문제들의 집합으로, 대표적인 예로 다항 시간 내에 풀 수 있는 문제의 클래스인 '''[[P (복잡도)|P]]''', 다항 시간 내에 해답을 검증할 수 있는 문제의 클래스인 '''[[NP (복잡도)|NP]]''' 등이 있다. 이러한 복잡도 클래스 간의 관계를 밝히는 것이 이 분야의 중심 과제이며, 그 가운데 가장 유명한 미해결 문제가 바로 '''[[P-NP 문제]]'''이다. 계산 복잡도 이론에서는 문제의 크기를 나타내는 입력 길이 ''n''에 대한 자원 사용량의 [[점근 분석|점근적 증가율]]을 분석한다. 이를 위해 [[대문자 O 표기법|빅오 표기법]]이 널리 사용되며, 다항 시간 ''O(n^k)''과 지수 시간 ''O(2^{n^k})'' 사이의 구분이 특히 중요하다. 일반적으로 다항 시간 내에 풀 수 있는 문제는 '''효율적으로 풀 수 있는''' 문제로 간주되고, 지수 시간이 필요한 문제는 '''다루기 어려운'''(intractable) 문제로 간주된다. == 역사 == === 초기 기반 (1930년대–1950년대) === 계산 복잡도 이론의 기원은 [[계산 가능성 이론]]에 뿌리를 두고 있다. 1936년 [[앨런 튜링]]이 [[튜링 기계]]의 개념을 제시하고, [[알론조 처치]]가 [[람다 대수]]를 발전시키면서 "계산 가능한 것이 무엇인가"라는 질문에 대한 형식적 틀이 마련되었다. 튜링은 [[정지 문제]]가 알고리즘적으로 풀 수 없음을 증명하여 계산의 근본적 한계를 보였다. 그러나 이 시기에는 계산 '''가능성'''에 초점이 맞추어져 있었고, 계산에 필요한 '''자원의 양'''에 대한 체계적 연구는 아직 이루어지지 않았다. 1950년대에 들어 [[존 폰 노이만]]과 다른 선구자들이 실제 컴퓨터를 구축하고 활용하면서, 이론적으로 계산 가능한 문제라 하더라도 실제로는 엄청난 시간이 걸릴 수 있다는 점이 분명해졌다. 이는 계산의 '''효율성'''에 대한 관심으로 자연스럽게 이어졌다. === 학문의 탄생 (1960년대) === 계산 복잡도 이론이 독립적 학문 분야로 탄생한 것은 1960년대이다. 1965년 [[주라이 하트마니스]](Juris Hartmanis)와 [[리처드 스턴스]](Richard Stearns)는 논문 「다중 테이프 튜링 기계의 계산 복잡도에 관하여」(''On the Computational Complexity of Algorithms'')를 발표하여, 시간과 공간 자원에 기반한 복잡도의 형식적 정의를 최초로 제시하였다. 이 논문에서 그들은 [[시간 계층 정리]]와 [[공간 계층 정리]]를 증명하여, 더 많은 자원을 허용하면 더 많은 문제를 풀 수 있음을 엄밀하게 보였다. 이 업적으로 두 사람은 1993년 [[튜링상]]을 공동 수상하였다. 같은 시기에 [[앨런 코밤]](Alan Cobham)은 1964년 논문에서 '''다항 시간'''의 개념을 '''효율적 계산'''과 동일시하는 관점을 처음으로 명확히 제시하였다. 이 아이디어는 이후 [[코밤의 논제]]로 알려지게 되었으며, [[잭 에드먼즈]]도 독립적으로 비슷한 관점을 주장하였다. === NP-완전성의 발견 (1970년대) === 1971년 [[스티븐 쿡]](Stephen Cook)은 역사적인 논문 「정리 증명 절차의 복잡도」(''The Complexity of Theorem-Proving Procedures'')에서 [[쿡-레빈 정리]]를 증명하였다. 쿡은 [불리언 충족 가능성 문제]가 '''[[NP-완전]]'''함을 보였는데, 이는 NP에 속하는 모든 문제가 SAT로 [[다항 시간 환원]]될 수 있음을 의미한다. 동시에 소비에트 연방의 수학자 [[레오니드 레빈]](Leonid Levin)도 독립적으로 동등한 결과를 얻었다. 1972년 [[리처드 카프]](Richard Karp)는 쿡의 결과를 크게 확장하여, [[부분 집합 합 문제]], [[그래프 색칠 문제]], [[해밀턴 경로 문제]] 등 21개의 중요한 조합 문제가 모두 NP-완전임을 증명하였다. 이 '''카프의 21개 NP-완전 문제'''는 NP-완전성이 단지 이론적 호기심이 아니라 실제 계산 문제에 광범위하게 나타나는 현상임을 보여주었으며, 복잡도 이론의 실용적 중요성을 확립하는 데 결정적 역할을 하였다. === 확장과 심화 (1980년대–1990년대) === 1980년대와 1990년대에는 복잡도 이론이 여러 방향으로 크게 확장되었다. 주요 발전은 다음과 같다. '''[[확률적 복잡도 클래스]]의 등장''': [[BPP]], [[RP]], [[ZPP]] 등 [[확률적 알고리즘]]의 능력을 포착하는 복잡도 클래스가 정의되고 연구되었다. '''[[대화형 증명 체계]]''': 1985년 [[셰피 골드바서]](Shafi Goldwasser), [[실비오 미칼리]](Silvio Micali), [[찰스 래코프]](Charles Rackoff)가 도입한 개념으로, 이후 [[IP (복잡도)|IP]] = [[PSPACE]]라는 놀라운 결과(1992년, [[아디 샤미르]])로 이어졌다. '''[[PCP 정리]]''': 1992년에 증명된 이 정리는 NP의 모든 문제가 확률적으로 검증 가능한 증명을 가진다는 것을 보여주었으며, [[근사 알고리즘]]의 한계에 대한 연구에 혁명적 영향을 미쳤다. '''[[계산 복잡도와 암호학]]''': 복잡도 이론의 가정, 특히 [[일방향 함수]]의 존재 가정이 현대 [[암호학]]의 이론적 기반으로 확립되었다. '''[[회로 복잡도]]''': [[불리언 회로]]의 크기와 깊이로 계산 복잡도를 측정하는 접근법이 발전하였다. === 현대적 발전 (2000년대 이후) === 21세기에 들어 계산 복잡도 이론은 더욱 다양한 방향으로 발전하고 있다. [[양자 컴퓨팅]]의 부상과 함께 [[BQP]] 등 [[양자 복잡도 클래스]]의 연구가 활발해졌다. 2019년에는 [[MIP*]] = [[RE (복잡도)|RE]]라는 결과가 발표되어, [[양자 얽힘]]을 활용한 다중 증명자 대화형 증명의 능력이 기존 예상을 훨씬 뛰어넘음이 밝혀졌다. 이 결과는 1976년 이래 미해결이었던 수학의 [[콘의 매장 문제]]를 부정적으로 해결하는 놀라운 결과로도 이어졌다. 또한 [[미세 구조 복잡도]](fine-grained complexity) 이론이 발전하여, [강지수 시간 가설]과 같은 보다 정교한 가정 하에서 구체적 문제의 정확한 복잡도를 밝히려는 시도가 이루어지고 있다. == 기본 개념 == === 계산 모델 === 복잡도 이론에서 가장 기본적인 계산 모델은 [[튜링 기계]]이다. 튜링 기계는 무한한 테이프, 읽기/쓰기 헤드, 유한한 상태 집합, 전이 함수로 구성되며, 알고리즘의 형식적 정의를 제공한다. 복잡도 이론에서는 이외에도 다양한 계산 모델이 사용된다. '''결정적 튜링 기계'''(DTM): 각 단계에서 하나의 가능한 동작만 수행하는 표준 튜링 기계 '''[[비결정적 튜링 기계]]'''(NTM): 각 단계에서 여러 가능한 동작 중 하나를 선택할 수 있는 튜링 기계로, NP 클래스의 정의에 핵심적으로 사용됨 '''[[확률적 튜링 기계]]''': 동전 던지기(난수)를 활용할 수 있는 튜링 기계 '''[[양자 튜링 기계]]''': [[양자역학]]의 원리에 기반한 계산 모델 '''[[불리언 회로]]''': 균일하지 않은(non-uniform) 계산 모델로, [[회로 복잡도]] 연구에 사용됨 '''[[오라클 기계]]''': 특정 문제를 단일 단계에서 풀 수 있는 오라클에 접근 가능한 튜링 기계 '''[[처치-튜링 논제]]'''에 따르면, 합리적인 모든 계산 모델은 서로 다항 시간 내에 시뮬레이션 가능하다는 것이 널리 받아들여지고 있으며, 이를 '''확장된 처치-튜링 논제'''(Extended Church-Turing Thesis)라 부른다. 그러나 양자 컴퓨팅의 등장은 이 확장된 논제에 도전을 제기하고 있다. === 결정 문제와 언어 === 복잡도 이론에서 문제는 주로 '''[[결정 문제]]'''의 형태로 다루어진다. 결정 문제란 "예" 또는 "아니오"로 답할 수 있는 문제를 의미하며, 형식적으로는 이진 문자열의 집합, 즉 '''[[형식 언어]]'''로 표현된다. 예를 들어 "주어진 [[그래프]]가 [[해밀턴 경로]]를 갖는가?"는 결정 문제이며, 해밀턴 경로를 갖는 그래프의 인코딩들의 집합이 해당 언어가 된다. 결정 문제 외에도 '''[[탐색 문제]]'''(해답을 찾는 문제), '''[[함수 문제]]'''(함수값을 계산하는 문제), '''[[계수 문제]]'''(해답의 개수를 세는 문제), '''[[최적화 문제]]''' 등이 연구된다. 이들 각각에 대응하는 복잡도 클래스가 별도로 정의되며, 예를 들어 계수 문제에 대한 클래스로 '''[[#P]]'''가 있다. === 환원 === '''[[환원]]'''(reduction)은 복잡도 이론에서 가장 핵심적인 기법 중 하나이다. 문제 A를 문제 B로 환원한다는 것은, B를 풀 수 있는 알고리즘을 이용하여 A를 풀 수 있음을 보이는 것이다. 이는 "B가 최소한 A만큼 어렵다"는 것을 의미한다. 주요 환원 유형은 다음과 같다. '''[[다항 시간 다대일 환원]]'''(Karp 환원): 문제 A의 각 인스턴스를 다항 시간에 문제 B의 인스턴스로 변환 '''[[다항 시간 튜링 환원]]'''(Cook 환원): 문제 B에 대한 오라클을 사용하여 문제 A를 다항 시간에 풀 수 있음 '''[[로그 공간 환원]]''': 로그 공간만을 사용하는 환원으로, P 내부의 세밀한 구조를 연구할 때 사용 환원을 통해 문제 간의 상대적 난이도를 비교할 수 있으며, 특정 복잡도 클래스에서 '''[[완전 (복잡도)|완전]]'''(complete) 문제를 정의하는 데 핵심적으로 사용된다. == 주요 복잡도 클래스 == === 시간 복잡도 클래스 === ==== P (다항 시간) ==== '''[[P (복잡도)|P]]'''는 결정적 튜링 기계로 다항 시간 내에 풀 수 있는 결정 문제의 클래스이다. 형식적으로, P = ∪_{k≥0} DTIME(n^k)이다. P에 속하는 문제의 예로는 [[정렬]], [[최단 경로 문제]], [[선형 계획법]], [[소수 판별]](2002년 [[AKS 소수 판별법]] 이후) 등이 있다. P는 일반적으로 "효율적으로 풀 수 있는" 문제의 클래스로 간주되며, 이를 '''코밤의 논제'''라 한다. ==== NP (비결정적 다항 시간) ==== '''[[NP (복잡도)|NP]]'''는 비결정적 튜링 기계로 다항 시간 내에 풀 수 있는 결정 문제의 클래스이다. 동등한 정의로, NP는 "예"인 경우에 다항 크기의 '''증거'''(certificate)가 존재하여 이를 다항 시간에 검증할 수 있는 문제의 클래스이다. 예를 들어 [[해밀턴 경로 문제]]는 NP에 속하는데, 경로가 주어지면 그것이 실제로 해밀턴 경로인지 다항 시간에 확인할 수 있기 때문이다. 모든 P 문제는 NP에도 속하므로 P ⊆ NP이지만, 그 역이 성립하는지 여부, 즉 P = NP인지 아닌지는 미해결이다. ==== NP-완전과 NP-난해 ==== '''[[NP-완전]]''' 문제는 NP에 속하면서 동시에 NP에 있는 모든 문제가 그것으로 다항 시간 환원 가능한 문제이다. 대표적 NP-완전 문제로는 [불리언 충족 가능성 문제], [[외판원 문제]]의 결정 버전, [[부분집합 합 문제]], [[그래프 색칠 문제]], [[배낭 문제]] 등이 있다. '''[[NP-난해]]'''(NP-hard) 문제는 NP의 모든 문제가 그것으로 환원 가능하지만, 그 자체가 NP에 속할 필요는 없는 문제이다. 즉, NP-완전 문제는 NP-난해이면서 동시에 NP에 속하는 문제이다. ==== EXPTIME과 그 이상 ==== '''[[EXPTIME]]'''은 결정적 튜링 기계로 지수 시간 O(2^{n^k}) 내에 풀 수 있는 문제의 클래스이다. P ⊊ EXPTIME이 증명되어 있으며(시간 계층 정리에 의해), EXPTIME-완전 문제의 예로는 일반화된 [[체스]]와 [[바둑]]의 최적 전략 결정 등이 있다. 이보다 더 큰 클래스로 '''[[2-EXPTIME]]''', '''[[ELEMENTARY]]''' 등이 존재한다. === 공간 복잡도 클래스 === ==== L과 NL ==== '''[[L (복잡도)|L]]'''(로그 공간)은 결정적 튜링 기계가 O(log n)의 작업 공간만으로 풀 수 있는 문제의 클래스이다. '''[[NL (복잡도)|NL]]'''은 비결정적 로그 공간 클래스이다. NL의 대표적 완전 문제로 [[방향 그래프]]에서의 [[도달 가능성 문제]]가 있다. [[사비치의 정리]]에 의해 NL ⊆ L² ⊆ P가 알려져 있으며, '''NL = co-NL'''이라는 놀라운 결과가 1988년 독립적으로 [[닐 임머만]]과 [[로베르트 쉘레프]]에 의해 증명되었다. ==== PSPACE ==== '''[[PSPACE]]'''는 다항 공간 내에서 풀 수 있는 문제의 클래스이다. P ⊆ NP ⊆ PSPACE ⊆ EXPTIME이 알려져 있지만, 이 포함 관계 중 어느 것이 진포함인지는 P ⊊ EXPTIME 외에는 증명되지 않았다. PSPACE-완전 문제의 예로는 [양화된 불리언 공식]의 참/거짓 판별이 있다. === 확률적 복잡도 클래스 === '''[[BPP]]''' (Bounded-error Probabilistic Polynomial time): 확률적 다항 시간 알고리즘으로 양쪽 오류 확률 1/3 이하로 풀 수 있는 문제 '''[[RP]]''' (Randomized Polynomial time): 한쪽 오류만 허용하는 확률적 다항 시간 클래스 '''[[ZPP]]''' (Zero-error Probabilistic Polynomial time): 기대 다항 시간 내에 항상 올바른 답을 내는 확률적 클래스로, ZPP = RP ∩ co-RP BPP와 P의 관계는 미해결이지만, 많은 전문가들은 BPP = P일 것으로 추측하고 있다. 이는 [[의사난수 생성기]]를 통한 역무작위화(derandomization) 연구와 밀접하게 관련된다. === 양자 복잡도 클래스 === '''[[BQP]]'''(Bounded-error Quantum Polynomial time)는 양자 컴퓨터로 다항 시간 내에 양쪽 오류 확률 1/3 이하로 풀 수 있는 문제의 클래스이다. BPP ⊆ BQP ⊆ PSPACE가 알려져 있다. [[쇼어의 알고리즘]]에 의해 [[정수 인수분해]]는 BQP에 속하지만, 이것이 P에 속하는지 여부는 미해결이다. 2019년 증명된 MIP* = RE 결과는 양자 복잡도 이론의 기념비적 성과로 평가된다. == P-NP 문제 == '''[[P-NP 문제]]'''는 계산 복잡도 이론의 가장 유명하고 중요한 미해결 문제이다. 이 문제는 "효율적으로 검증할 수 있는 문제는 모두 효율적으로 풀 수도 있는가?"를 묻는다. 형식적으로는 복잡도 클래스 P와 NP가 동일한지 여부를 묻는 문제이다. 2000년 [[클레이 수학 연구소]]는 P-NP 문제를 7개의 '''[[밀레니엄 현상 문제]]''' 중 하나로 선정하고 100만 달러의 상금을 걸었다. 대부분의 전문가는 P ≠ NP일 것으로 믿고 있지만, 2025년 현재까지 이를 증명하지도, 반증하지도 못하고 있다. P ≠ NP가 참이라면, NP-완전 문제에 대한 효율적 알고리즘은 존재하지 않으며, 이는 현대 [[공개 키 암호|공개 키 암호 체계]]의 안전성을 뒷받침하는 근거가 된다. 반대로 P = NP가 증명된다면, 현재의 암호 체계 대부분이 무력화될 수 있으며, [[최적화]], [[인공지능]], [[신약 개발]] 등 다양한 분야에 혁명적 변화가 일어날 것이다. === 증명의 장벽 === P ≠ NP 증명이 극도로 어려운 이유를 설명하는 여러 '''장벽'''(barrier) 결과가 알려져 있다. '''[[상대화 장벽]]'''(Relativization barrier): 1975년 [[테드 베이커]], [[존 길]], [[로버트 솔로베이]]는 어떤 오라클 A에 대해 P^A = NP^A이고, 다른 오라클 B에 대해 P^B ≠ NP^B임을 보였다. 따라서 오라클에 대해 상대화되는 증명 기법으로는 P-NP 문제를 해결할 수 없다. '''[[자연 증명 장벽]]'''(Natural proofs barrier): 1994년 [[알렉산더 라즈보로프]]와 [[스티븐 루디히]]는 특정 암호학적 가정 하에서, "자연적"인 성질을 만족하는 증명 기법으로는 회로 하한을 증명할 수 없음을 보였다. '''[[대수화 장벽]]'''(Algebrization barrier): 2009년 [[스콧 에런슨]]과 [[아비 위그더슨]]이 도입한 장벽으로, 상대화 장벽의 확장이다. == 주요 정리와 결과 == === 계층 정리 === '''[[시간 계층 정리]]'''와 '''[[공간 계층 정리]]'''는 복잡도 이론의 기본 정리로, 더 많은 자원을 허용하면 엄격하게 더 많은 문제를 풀 수 있음을 보장한다. 예를 들어 시간 계층 정리에 의해 DTIME(n²) ⊊ DTIME(n³)이 성립한다. === 사비치의 정리 === '''[[사비치의 정리]]'''(1970)는 비결정적 공간 S(n)으로 풀 수 있는 모든 문제가 결정적 공간 O(S(n)²)으로 풀 수 있음을 보인다. 이는 NSPACE(S(n)) ⊆ DSPACE(S(n)²)를 의미하며, 공간 복잡도에서 비결정성의 이점이 제곱 이하임을 보여준다. === IP = PSPACE === 1992년 [[아디 샤미르]]는 '''[[IP (복잡도)|IP]]''' = '''[[PSPACE]]'''를 증명하였다. 이는 대화형 증명 체계의 능력이 다항 공간 계산과 정확히 일치함을 보여주는 깊은 결과이다. === PCP 정리 === '''[[PCP 정리]]'''는 NP = PCP(O(log n), O(1))로 표현되며, NP의 모든 문제가 O(log n)개의 랜덤 비트와 상수 개의 쿼리로 검증 가능한 확률적 증명을 가짐을 의미한다. 이 정리는 [[근사 불가능성 결과]]의 핵심 도구가 되었다. == 응용 분야 == === 암호학 === 현대 [[암호학]]은 계산 복잡도 이론에 깊이 의존하고 있다. [[RSA 암호]], [[디피-헬만 키 교환]] 등 [[공개 키 암호]] 체계의 안전성은 [[정수 인수분해]]나 [[이산 로그 문제]]가 다항 시간에 풀리지 않는다는 가정에 기반한다. [[일방향 함수]]의 존재는 P ≠ NP보다 강한 가정이지만, 이것이 확인된다면 안전한 암호 체계를 구성할 수 있음이 증명되어 있다. === 알고리즘 설계 === 복잡도 이론의 결과는 [[알고리즘]] 설계에 직접적 지침을 제공한다. 문제가 NP-난해로 밝혀지면, 정확한 해를 구하는 다항 시간 알고리즘의 존재 가능성이 낮으므로, [[근사 알고리즘]], [[매개변수화 알고리즘]], [[무작위 알고리즘]], [[휴리스틱]] 등 대안적 접근법을 모색하게 된다. === 데이터베이스와 검증 === [[데이터베이스]] 질의 최적화, [[형식 검증]], [[모델 검사]] 등 실용적 분야에서도 복잡도 분석은 핵심적이다. 문제의 복잡도를 파악함으로써 확장 가능한 시스템을 설계하고, 실용적으로 다루기 어려운 경우를 미리 식별할 수 있다. === 인공지능과 기계학습 === [[인공지능]]과 [[기계학습]]의 여러 문제도 복잡도 이론의 관점에서 분석된다. [[계산 학습 이론]]에서는 학습 문제의 복잡도를 연구하며, 특정 학습 과제가 본질적으로 어려운지를 파악하는 데 복잡도 이론적 도구가 활용된다. == 영향 및 의의 == 계산 복잡도 이론은 [[컴퓨터 과학]]뿐 아니라 [[수학]], [[물리학]], [[경제학]] 등 다양한 분야에 심대한 영향을 미쳤다. 수학에서는 복잡도 이론이 [[증명 복잡도]]와 [[기술적 집합론]]의 문제들과 깊은 연관을 맺고 있으며, MIP* = RE 결과가 [[콘의 매장 문제]]를 해결한 사례는 계산 이론과 순수 수학의 놀라운 연결을 보여준다. 물리학에서는 양자 복잡도 이론이 [[양자 정보 이론]] 및 [[블랙홀 정보 역설]]과 관련된 논의에서 중요한 역할을 하고 있다. 경제학에서는 [[알고리즘 게임 이론]]이 발전하여, [[내시 균형]]의 계산 복잡도 연구(PPAD-완전성) 등이 경제학적 모델의 계산 가능성에 대한 새로운 시각을 제공하고 있다. 이 분야의 연구자 여럿이 [[튜링상]], [[괴델상]], [[네반린나상]] 등 최고 권위의 상을 수상하였으며, 이는 이 분야의 학술적 중요성을 방증한다. == 논란 및 비평 == === 코밤의 논제에 대한 비판 === "다항 시간 = 효율적"이라는 코밤의 논제에 대해서는 오랜 비판이 존재한다. 이론적으로 다항 시간이더라도 ''n''의 매우 높은 거듭제곱(예: n^{100})은 실용적으로 전혀 효율적이지 않을 수 있다. 반대로, 지수 시간 알고리즘이라도 실제 인스턴스에서는 빠르게 작동하는 경우가 많다. 대표적으로 [[단체법]]은 최악의 경우 지수 시간이지만, 실무에서는 매우 효율적으로 작동한다. === 최악의 경우 분석의 한계 === 복잡도 이론은 전통적으로 '''최악의 경우'''(worst-case) 분석에 초점을 맞추지만, 이것이 실제 문제의 난이도를 제대로 반영하지 못한다는 비판이 있다. [[평균 경우 복잡도]], [[평활 분석]](smoothed analysis) 등 대안적 분석 프레임워크가 제안되어 활발히 연구되고 있다. === 증명의 진전 부재 === P-NP 문제를 비롯한 핵심 미해결 문제들이 수십 년간 풀리지 않고 있다는 점은 이 분야의 방법론적 한계를 드러내는 것으로 볼 수 있다. 여러 장벽 결과들은 기존의 증명 기법으로는 이 문제들을 해결할 수 없음을 시사하며, 근본적으로 새로운 접근법이 필요할 수 있다. === 이론과 실무의 괴리 === 일부 실무자들은 복잡도 이론이 지나치게 추상적이어서 실제 소프트웨어 공학이나 알고리즘 엔지니어링에 직접적 도움이 되지 않는다고 비판한다. 그러나 복잡도 이론 연구자들은 이론이 장기적으로 실무에 영향을 미치며, 암호학과 최적화에 미친 영향이 그 대표적 사례라고 반론한다. == 관련 문서 == [[계산 이론]] [[계산 가능성 이론]] [[알고리즘]] [[P-NP 문제]] [[튜링 기계]] [[복잡도 클래스]] [[NP-완전]] [[암호학]] [[양자 컴퓨팅]] [[알고리즘 분석]] [[회로 복잡도]] [[근사 알고리즘]] [[대화형 증명 체계]] [[계산 학습 이론]] [[알고리즘 게임 이론]] == 외부 링크 == [https://complexityzoo.net/ Complexity Zoo - 복잡도 클래스의 포괄적 목록] [https://www.claymath.org/millennium-problems/p-vs-np-problem 클레이 수학 연구소 - P vs NP 문제] [https://www.scottaaronson.com/blog/ 스콧 에런슨 블로그 - 복잡도 이론 관련 논의] [[분류:이론 컴퓨터 과학]] [[분류:계산 복잡도 이론]] [[분류:수학]] [[분류:미해결 문제]]