AI Study
하트마니스·스턴스·쿡·카프·레빈이 정립한 자원 효율의 수학 — P vs NP 난제에서 트랜스포머 O(N²) 병목 돌파까지

계산 복잡도 이론 (Computational Complexity Theory)

AI(인공지능) 분야에서 계산 복잡도 이론(Computational Complexity Theory) 은 인공지능 알고리즘이 문제를 해결하는 데 필요한 시간과 메모리(자원)의 한계를 수학적으로 분석하고 분류하는 학문입니다.
쉽게 말해 AI 가 특정 문제를 현실적인 시간 내에 풀 수 있는지, 아니면 우주의 나이보다 더 오랜 시간이 걸리는 '사실상 불가능한 문제'인지를 판단하는 기준을 제공합니다. AI 연구와 개발에서 이 이론이 가지는 핵심적인 의미는 다음과 같습니다.

1. AI 문제의 난이도 판별 (P vs NP 문제)

AI 가 해결하려는 대부분의 고차원적인 문제들은 계산 복잡도가 매우 높습니다.

  • NP-난해(NP-hard) / NP-완전(NP-complete) 문제: 경로 탐색(외판원 문제), 논리적 추론, 스케줄링, 단백질 구조 예측 등은 데이터의 양이 조금만 늘어나도 계산량이 기하급수적으로 폭발합니다.
  • 역할: 계산 복잡도 이론은 이러한 문제들이 기존 컴퓨터로 '완벽한 정답'을 빠르게 찾는 것이 수학적으로 거의 불가능함을 증명해 줍니다.
2. AI 연구 방향의 전환 (완벽함에서 근사치로)

특정 AI 문제가 계산 복잡도 이론상 '너무 어렵다(Intractable)' 고 판명되면, 연구자들은 완벽한 해답을 찾는 것을 포기하고 다른 전략을 세웁니다.

  • 휴리스틱(Heuristic) 및 근사 알고리즘: 완벽한 정답 대신 '충분히 좋은 정답'을 빠르게 찾는 방법을 사용합니다. 체스나 바둑 AI 가 모든 경우의 수를 계산하지 않고 유망한 수만 탐색하는 것이 대표적입니다.
  • 딥러닝과 확률적 접근: 복잡한 규칙을 일일이 논리적으로 계산하는 대신, 데이터를 통해 패턴을 학습하여 확률적으로 가장 그럴싸한 답을 내놓는 딥러닝 방식이 발전한 배경이기도 합니다.
3. 신경망 학습의 한계와 가능성 규명

현대 AI의 핵심인 딥러닝(인공신경망) 자체도 계산 복잡도 이론의 연구 대상입니다.

  • 학습의 어려움: 최적의 신경망 가중치를 찾는 과정 자체는 수학적으로 NP-완전 문제에 속할 만큼 어렵습니다.
  • 해결의 실마리: 그럼에도 불구하고 현재 AI가 잘 작동하는 이유는 '경사 하강법(Gradient Descent)' 같은 최적화 기법과 대규모 데이터, 그리고 GPU 병렬 연산이 결합하여 복잡도의 벽을 실용적으로 우회하고 있기 때문입니다.
4. 모델 경량화 및 효율성 평가

오늘날 거대언어모델(LLM) 등이 엄청난 연산 자원을 소모하면서 계산 복잡도의 중요성이 더욱 커졌습니다.

  • 시간 및 공간 복잡도: 모델이 추론(Inference) 할 때 걸리는 시간과 필요한 메모리(VRAM)를 Big-O 표기법 등으로 분석하여, 스마트폰 같은 작은 기기에서도 AI가 돌아갈 수 있도록 모델을 압축(양자화, 가지치기 등)하는 기준이 됩니다.
요약

AI 에게 계산 복잡도 이론은 "무엇을 계산할 수 있고, 무엇을 포기해야 하는지 알려주는 나침반"입니다. 이 이론 덕분에 AI 는 무모한 완벽주의(모든 경우의 수 계산) 에서 벗어나, 현실적인 시간 안에 작동하는 지능적인 근사치와 학습 모델을 만드는 방향으로 진화할 수 있었습니다.

계산 복잡도 이론(Computational Complexity Theory)은 "원리적으로 풀 수 있는 문제라도 현실적인 시간(Time), 메모리(Space), 병렬 프로세서, 양자 자원으로 해결할 수 있는가?"를 수학적으로 분류하는 계산이론(Theory of Computation)의 핵심 영역입니다. 현대 AI와 대규모 언어 모델(LLM)에서 어텐션의 O(N2) 연산 한계, KV 캐시 메모리 폭발, 단일 패스 TC0 회로 장벽, 그리고 CoT와 Test-Time Compute가 이를 극복하는 원리가 모두 계산 복잡도 이론의 정밀한 분석 위에서 탄생했습니다.

SECTION 01

AI 관점에서 본 Computational Complexity Theory의 개념

계산가능성 이론이 "무한한 시간·메모리를 줄 때 풀 수 있는가?"라는 존재성 질문이라면, 계산 복잡도 이론은 "입력 크기 N(문맥 토큰 수, 그래프 노드 수, 데이터셋 크기)이 커질 때 필요한 시간·메모리·통신 자원이 어떻게 폭증하는가?"를 Big-O 점근 표기법과 복잡도 부류(Complexity Classes)로 측정합니다. AI 시스템의 성패는 결국 이 자원 비용이 현실적인 GPU·전력·지연 시간 한계 내에 들어오는가에 달려 있습니다.

자원 ① · 시간 복잡도 (Time)

O(N) vs O(N2) vs O(2N)

컨텍스트 길이 N이 10배 늘면 선형(O(N)) 모델은 10배, 표준 트랜스포머 어텐션(O(N2))은 100배, 조합 탐색(O(2N))은 천문학적으로 폭증합니다. AI 모델 규모 확장을 지배하는 제1지표입니다.

자원 ② · 공간 & I/O 복잡도

VRAM · KV Cache · HBM I/O

연산 횟수보다 메모리 공간과 대역폭 이동(I/O Complexity)이 병목이 되는 경우가 많습니다. 긴 문맥 LLM의 KV Cache 공간 증가와 FlashAttention의 SRAM 타일링이 대표적입니다.

자원 ③ · 병렬 회로 복잡도

TC0 · NC vs 순차 P

수만 개 GPU 코어로 동시 계산 가능한 문제는 NC 또는 상수 깊이 임계 회로 TC0에 속합니다. 단일 패스 트랜스포머가 TC0에 갇혀 순차 추론에 약한 근본 이유입니다.

자원 ④ · 난이도 부류 (P vs NP)

P vs NP · NP-hard · BQP

정확한 신경망 전역 학습·베이지안 정확 추론·조합 계획은 NP-complete 또는 NP-hard입니다. AI는 이를 피하기 위해 근사·경사하강·검증기 탐색을 택합니다.

INFOGRAPHIC 01 · AI 관점 계산 복잡도 계층(Complexity Zoo) & 자원 스케일링 지도 복잡도 부류별로 어떤 AI 연산·모델·추론 방식이 위치하는지 한눈에 비교
Computational Complexity Theory × AI : 복잡도 계층과 인공지능 연산 지도 "단일 패스 GPU 병렬(TC⁰) ➔ 다항 시간(P / CoT) ➔ 탐색·검증 비대칭(NP) ➔ 게임·계획 공간(PSPACE) ➔ 지수 장벽(EXPTIME)" EXPTIME / EXPSPACE (지수 시간·공간) — 우주의 나이보다 긴 완전 탐색 영역 (2ᴺ, N!) 완전 바둑·체스 일반화 해법 · 무제한 조합 최적화 ➔ AI 해결 전략: AlphaZero MCTS + 가치망(Value Net)으로 탐색 가지치기 PSPACE (다항 메모리 공간) — 장기 다단계 에이전트 계획 · QBF · POMDP NP / NP-Complete / #P — "생성(찾기)은 지수적으로 어려우나, 다항 시간(P) 검증이 가능한 핵심 AI 난제" • 3-노드 신경망 전역 최적 학습(Blum-Rivest) · 일반 베이지안 네트워크 정확 추론(#P-hard) · SAT · TSP · 수학 정리 탐색 BQP (양자 다항 시간) P ⊆ BPP ⊆ BQP ⊆ PSPACE • 양자 선형대수 · 샘플링 • 쇼어 알고리즘 (소인수분해) 주의: NP-Complete를 모두 즉시 푼다고 보장되진 않음 (그로버 탐색은 √N 제곱근 가속) P (Polynomial Time) — 현실적 다항 시간 해결 가능 영역 SGD 1스텝 역전파 · 어텐션 O(N²) / SSM O(N) · CoT 다단계 추론 · 컴파일러/단위테스트 검증 NC (Nick's Class) — GPU 대량 병렬 폴리로그 시간 (O(logᵏ N)) TC⁰ (상수 깊이 병렬 임계 회로) = 단일 패스 트랜스포머 LLM 1-Pass는 매우 빠르나 순차 상태 추적 불가 ➔ 다항 시간 CoT 토큰으로 P 확장
SECTION 02 · DEEP RESEARCH

AI와 LLM에서 Computational Complexity Theory이 중요한 5대 이유

최근 생성형 AI와 LLM 경쟁의 본질은 단순 파라미터 확장을 넘어 "동일한 연산·메모리 예산(FLOPs & HBM Bandwidth) 안에서 복잡도 장벽을 얼마나 영리하게 우회하고 돌파하는가"로 이동했습니다. Deep Research 관점에서 계산 복잡도 이론이 AI·LLM의 핵심 무기인 5가지 이유를 분석합니다.

핵심 분석 01 · 이차(Quadratic) 병목 돌파

Self-Attention의 O(N2) 장벽, I/O 복잡도, 그리고 FlashAttention · Mamba 혁신

표준 트랜스포머 어텐션은 문맥 길이 N에 대해 모든 토큰 쌍을 내적하므로 O(N2) 시간·메모리 복잡도를 가집니다. 4K 토큰이 1M(백만) 토큰으로 250배 늘어나면 단순 연산량은 2502 = 62,500배로 치솟습니다. 게다가 미세입자 복잡도 이론(Fine-Grained Complexity, Alman & Song 2023)은 강력한 지수 시간 가설(SETH) 아래 임의 정밀도 어텐션 계산이 원리적으로 서브이차(Sub-quadratic) 시간으로 축소될 수 없음을 증명해, 무조건적 정확 어텐션 최적화의 한계를 밝혔습니다.

이 복잡도 하한이 오히려 혁신을 낳았습니다. FlashAttention은 FLOPs가 아닌 I/O 복잡도(Slow HBM ⇄ Fast SRAM 이동 횟수)를 타일링으로 극소화해 O(N2) 행렬을 HBM에 기록하지 않고 처리했으며, Mamba(SSM) · Linear Attention은 고정 크기 상태 압축을 통해 학습 O(N) · 토큰당 추론 O(1) 복잡도를 달성했습니다.

핵심 분석 02 · 회로 복잡도와 CoT

트랜스포머 단일 패스(TC0) 한계와 Test-Time Compute(CoT)의 복잡도 승격

병렬 레이어를 고정 깊이(예: 80층)만 통과시키는 단일 Forward Pass LLM은 회로 복잡도 부류인 TC0(상수 깊이 임계 게이트 회로) 안에 갇힙니다. TC0는 순차적 깊이 의존성이 있는 NC1-완전(예: 부울 수식 평가, 짝수/홀수 패리티 일반화)이나 P-완전 문제를 풀 수 없습니다. 반면 모델이 Chain-of-Thought(CoT)로 다항 개수 T(N)개의 중간 추론 토큰을 생성하면, 시간 복잡도 예산을 지불하는 대신 모델의 계산 복잡도 계층 자체를 TC0 ➔ P(다항 시간 순차 연산)로 승격시킵니다. 이것이 바로 OpenAI o1/o3, DeepSeek-R1 등 추론 모델이 사고 시간을 늘릴수록 수학·코딩 정답률이 급상승하는 복잡도 이론적 근거입니다.

핵심 분석 03 · NP-Hard 회피 전략

학습의 NP-Hard 벽 돌파: 경사 하강법 근사 & P-검증기 비대칭성

단 3개의 은닉 노드를 가진 단순 신경망조차 학습 데이터를 100% 완벽히 맞추는 전역 최적 가중치를 찾는 문제는 NP-complete(Blum & Rivest, 1988)이며, 일반 그래프 확률 모델(Bayesian Network)의 정확한 사후 확률 추론 역시 #P-hard입니다. 현대 딥러닝은 이 지수 복잡도(2N)를 이산 조합 탐색으로 정면 돌파하려 하지 않고, 미분 가능한 연속 공간으로 완화(Relaxation)해 역전파 O(P) · 확률적 경사 하강법(SGD)으로 "충분히 좋은 지역 최적해"를 찾는 전략으로 성공했습니다. 나아가 검증이 P 시간에 끝나는 영역에서는 RLVR(검증 가능 보상 강화학습) · AlphaProof가 NP-어려움(탐색)을 효율적으로 공략합니다.

핵심 분석 04 · 조건부 연산과 추론 가속

MoE · KV Cache 압축 · Speculative Decoding의 복잡도 공학

초거대 밀집(Dense) 모델은 토큰 하나를 생성할 때마다 전체 파라미터 W를 VRAM에서 로드해야 하므로 메모리 대역폭 복잡도가 막대합니다. MoE(Mixture of Experts)는 전체 지식을 E개 전문가에 분산하되 토큰당 상위 k개만 활성화해 모델 용량과 추론 FLOPs 복잡도를 분리합니다. 또한 자기회귀 디코딩의 순차 O(K) 지연 병목을 극복하는 투기적 디코딩(Speculative Decoding)은 가벼운 드래프트 모델의 직렬 예측을 큰 모델의 단일 병렬 NC-친화 검증 배치(Verification Batch)로 전환해 생성 품질 손실 없이 추론 지연 복잡도를 수 배 낮춥니다.

핵심 분석 05 · 샘플 복잡도와 보안

PAC 학습 샘플 복잡도 · 양자 AI 경계 · 추론 비용(Overthinking) 방어

통계적 학습 이론(PAC Learning)은 목표 오차 이내의 일반화를 위해 필요한 데이터 크기인 샘플 복잡도(Sample Complexity)를 다루며, 계산 복잡도와 결합해 "다항 데이터는 있어도 다항 시간 내 학습이 불가능한 암호학적 함수"의 존재를 보여줍니다. 또한 최근 에이전트·추론 LLM에서는 악의적 입력으로 모델의 CoT 토큰 생성을 끝없이 늘려 최악 시간 복잡도(Worst-Case Latency/Cost)를 고갈시키는 Sponge / Overthinking 공격을 방어하기 위해 복잡도 기반 조기 종료와 비용 상한 설계가 필수입니다.

AI · LLM 연산 영역 기존 복잡도 병목 복잡도 이론 기반 해결 아키텍처
긴 문맥 어텐션 (Long Context) 시간·공간 O(N2) & HBM I/O 병목 FlashAttention(SRAM 타일링 I/O 최소화), GQA/MLA, Mamba(O(N))
단일 순전파 표현력 한계 상수 깊이 병렬 회로 TC0 정체 Chain-of-Thought(CoT) · Test-Time Compute ➔ P 시간 확장
전역 신경망 학습 & 조합 계획 NP-complete / NP-hard (2N) 연속 완화 SGD 근사 + AlphaZero MCTS + Lean4/테스트 P-검증기
자기회귀 추론 지연 시간 Dense O(W) 메모리 로드 & 직렬 O(K) 생성 Sparse MoE(활성 파라미터 축소) + Speculative Decoding + INT4/FP4
에이전트 · 추론 모델 안정성 최악 토큰 폭증(Overthinking DoS) 동적 난이도 라우팅(Easy→Fast, Hard→CoT) 및 토큰/스텝 상한 제어
INFOGRAPHIC 02 · LLM 복잡도 병목(Bottleneck) ➔ 아키텍처 돌파 지도 복잡도 이론의 수학적 한계가 어떻게 현대 AI 핵심 기술들을 탄생시켰는지 도식화
LLM 4대 복잡도 병목 ➔ 계산 복잡도 이론 기반 돌파 해법 "모든 AI 엔지니어링 최적화의 이면에는 시간·공간·I/O·회로·NP 복잡도 트레이드오프가 존재한다" ① 문맥 길이 벽 : 어텐션 O(N²) ➔ I/O · 선형화 돌파 기존 병목 (Quadratic) 연산 O(N²) · 메모리 O(N²) SETH 하한: 정확 어텐션은 임의 벡터에서 서브이차 불가 1M 토큰 시 HBM I/O 마비 복잡도 기반 해법 • FlashAttention (SRAM 타일링) ➔ HBM I/O 복잡도 최소화 • Mamba / Linear SSM ➔ 학습 O(N) · 추론 O(1) ② 추론 깊이 벽 : 단일 패스 TC⁰ ➔ CoT 시간 교환 1-Pass 회로 한계 복잡도 부류 : TC⁰ 깊이 고정 병렬 레이어는 NC¹ / P-완전 순차 상태 추적·심층 논리 즉답 불가 Test-Time Compute • T(N)개 CoT 토큰 생성 • 시간 O(T(N)) 비용 지불로 계산 능력 ➔ P 영역 승격 • o1/o3 · R1 추론 스케일링 ③ 최적화·탐색 벽 : NP-Hard ➔ 연속 근사 + P-검증 조합 폭발 난제 NP-Complete / #P-Hard 이산 전역 최적 가중치 탐색, 정확 베이지안 추론, TSP 등은 완전 탐색 시 지수 시간(2ᴺ) 현실적 다항 근사 • 연속 완화 + SGD 역전파 O(P) • MCTS 휴리스틱 탐색 절단 • P-검증기(Lean4/Unit Test) 기반 강화학습 (RLVR) ④ 서빙·대역폭 벽 : Dense O(W) ➔ 조건부 · 병렬 검증 추론 서빙 병목 Memory Bandwidth Bound 매 토큰 생성마다 수백 GB 가중치 로드 + 순차 O(K) 자기회귀 직렬 지연 발생 서빙 복잡도 최적화 • Sparse MoE (활성 k/E 축소) • Speculative Decoding (순차 생성 ➔ 1회 병렬 검증) • GQA/MLA + INT4 양자화
SECTION 03 · FOR AI ENGINEERS

AI 개발자들에게 Computational Complexity Theory가 가지는 5대 실무 의미

현업 AI 개발자에게 계산 복잡도 이론은 학문적 장식이 아니라 클라우드 GPU 비용을 10분의 1로 줄이고, 응답 지연을 제어하며, LLM이 엉뚱한 조합 문제에서 실패하지 않도록 시스템을 설계하는 실전 무기입니다.

실무 의미 01

컨텍스트 폭증(O(N2))과 KV Cache 예산 설계

모든 문서를 프롬프트에 통째로 넣으면 Prefill O(N2) 연산과 선형 증가하는 KV Cache 메모리가 폭발합니다. 복잡도를 아는 AI 개발자는 RAG 검색(Top-K 축소), 컨텍스트 압축, Prompt Caching을 조합해 N을 작게 유지합니다.

실무 의미 02

Compute-Bound vs Memory-Bandwidth-Bound 진단

Prefill(대규모 행렬곱)은 FLOPs가 병목이지만, Decoding(토큰 1개씩 순차 생성)은 GPU VRAM 대역폭 I/O가 병목입니다. 따라서 개발자는 Continuous Batching, MoE, 양자화(INT4/FP8), Speculative Decoding을 적재적소에 선택할 수 있습니다.

실무 의미 03

NP-Hard 조합 문제는 LLM이 아닌 전문 솔버로 위임

일정 배정, 물류 경로(TSP), 제약 충족 퍼즐처럼 NP-complete 본질을 지닌 문제에 LLM을 그대로 쓰면 환각이 발생합니다. AI 개발자는 LLM이 문제를 수식으로 정식화하게 두고 실제 풀이는 OR-Tools, Z3 SAT 솔버, Python 최적화 라이브러리에 위임합니다.

실무 의미 04

난이도 기반 동적 라우팅 (TC0 빠른 모델 vs CoT)

단순 요약·분류처럼 TC0 1-Pass로 충분한 질의에 비싼 Thinking 토큰을 태우면 레이턴시와 비용이 낭비됩니다. 작업의 순차 깊이 복잡도를 판별해 경량 모델과 추론 모델(Test-Time Compute)로 자동 라우팅하는 것이 핵심 역량입니다.

실무 의미 05

분산 학습·추론 통신 복잡도 최적화 및 최악 비용(Worst-Case) 방어

다중 GPU 환경(Tensor/Pipeline/Data Parallelism)에서는 노드 간 All-Reduce 통신 복잡도가 전체 학습 속도를 좌우합니다. 또한 프로덕션 에이전트에서는 사용자가 의도적으로 거대 입력이나 무한 추론 체인을 유발해 토큰·GPU 자원을 고갈시키지 않도록 최대 컨텍스트·추론 토큰·도구 호출 타임아웃 상한을 복잡도 분석에 기반해 설정해야 합니다.

SECTION 04 · ARCHIVE PRESERVATION

원전 해설 및 P vs NP 아카이브 (원본 보존)

서구 계산 이론의 전통에서 계산의 복잡도라는 개념은 논리학과 Alan Turing 이 제시한 '계산 가능성' 의 연구 결과에 뿌리를 두고 있다

복잡도 이론 (Complexity Theory) 은 주어진 문제를 풀기위해 계산과정에 필요로 하는 자원을 다루는 계산이론 (Theory of Computation) 의 일부이다. 가장 흔한 자원은 시간 (문제를 풀기위해 얼마나 많은 단계를 거치게 되는가) 와 공간 (문제를 풀기위해 얼마나 많은 메모리를 필요로 하는가) 이다. 이외에도 문제를 병렬적으로 풀기위해 얼마나 많은 병렬 프로세서가 필요한가 와 같은 다른 자원들이 고려될 수 있다. Complexity theory 는 필요한 자원과는 무관하게 어떤 문제를 풀 수 있는지 없는지를 다루는 계산가능성 이론 (Computability Theory) 과는 다르다.

단 하나의 "문제" 는 관련 질문들의 전체 집합이며, 이때 질문은 유한 길이의 문자열이다. 예를들면 인수분해 (factorize) 문제에서, 이진법으로 쓰여진 정수가 주어지고, 그 수의 소인수를 전부 반환한다. 어떤 특별한 질문을 instance 라고 부른다. 예를들면 "15 의 인수들을 구해라" 하는 것은 인수분해 문제의 한 instance 이다.

시간 복잡도 (time complexity) 는 가장 효율적인 (보통 bit 로서 측정된다) 알고리즘을 사용해서 한 문제의 instance 를 푸는데 걸리는 단계의 수를 의미한다. 즉 n bit 길이의 instance 가 n2 단계 내에 풀릴 수 있다면 그 문제는 n2 의 시간 복잡도를 가진다고 말한다. 물론 단계의 정확한 수는 사용되는 기계나 언어에 의존할 것이다. 그런 문제를 피하기 위해 보통 Big O notation 을 사용한다. 만일 어떤 문제가 일반적인 컴퓨터에서 시간 복잡도 O(n2) 를 가진다면, 대부분의 다른 컴퓨터에서도 복잡도 O(n2) 를 가질 것이므로, 이러한 notation 은 특별한 컴퓨터에 구애받지 않고 일반화 할 수 있게 해준다.

예) 잡초 깎기는 두배의 면적을 깎는데는 두배의 시간이 걸리기 때문에 선형 (linear) 복잡도를 가진다. 그러나 사전에서 어떤 것을 찾을 때, 두배 크기의 사전의 경우에 사전을 한번 이상 더 열어봐야 하기 때문에 지수 (logarithmic) 복잡도를 가진다 (예를들어 정확하게 중간이라면 그 문제는 반으로 감소한다)

복잡도 이론으로 유명한 인물은 Juris Hartmanis, Richard Stearns, Stephen Cook, Richard Karp, Leonid Levin 등이 있다. 그들은 대부분 Alan Turing 상 을 수상했다. Cook 는 1971 년에 논문 "The Complexity of Theorem Proving Procedures"에서 NP-completeness 를 정의하고 boolean satisfiability problem 는 NP-complete 이다 라는 증명을 하였다. 그 논문으로 P 와 NP 복잡도가 같은 것인지 아닌지 (즉 NP = P 인지) 하는 컴퓨터 과학의 위대한 미해결 문제를 열어놓았고, 그것에 대한 대답을 발견하지 못하고 있다.

즉 'NP-complete 가 철저한 조사를 필요로 하는가 아니면 필요로하지 않는가?' 라는 문제이다. 그것을 다른 식으로 표현하면 다음과 같다. 즉, 세일즈맨의 여행 문제와 같은 문제들에 대해 가능한 경로들 가운데 오로지 어떤 작은 부분만을 검토하면서 그 문제를 해결할 수 있는 알고리즘 이 컴퓨터 과학의 역사를 변화시킬 것이란 이야기이다.

Juris Hartmanis 와 Richard Stearns 은 계산 복잡도 이론 분야의 기초를 놓은 논문 On the computational complexity of algorithms (1965) 을 발표했다. ........... (Wikipedia : Computational Complexity Theory)

복잡성 이론에서는 알고리즘의 속도가 다항식으로 표현되는 문제들을 묶어서 'P' 라고 부르고, 다항식으로 표현될 수 있는지 여부가 알려지지 않은 문제들을 묶어서 'NP' 라고 부른다. 여기서 P 는 Polynomial (다항식) 의 머리 글자고, NP 는 nondeterministic polynomial (비결정성 다항식) 의 머리 글자를 의미한다. 이때 NP 가 non-polynomial (비다항식) 을 의미하지 않는다는 사실에 유의할 필요가 있다. 다항식이 아니라는 사실과 다항식으로 표현되는지 여부가 아직 알려지지 않았다는 사실 사이에는 엄청난 차이가 존재하기 때문이다. 다항식으로 표현되는 알고리즘은 오늘날의 컴퓨터가 적당한 시간내에 해결할 수 있는 문제기 때문에 P 에 속한 문제들은 '쉬운' 문제들이고, NP 는 그와 반대로 '어려운' 문제를 의미한다.

복잡성 문제를 연구하는 학자들에게 가장 어려운 질문중의 하나는 바로 "NP 에 속하는 문제들이 궁극적으로는 모두 다항식, 즉 쉬운 알고리즘을 이용해서 해결될 수 있을까?" 라는 질문이다. 만약 그렇다면 NP 에 속한 문제나 P 에 속한 문제가 모두 종국에는 다항식으로 표현되기 때문에 'P = NP' 라는 등식이 성립하게 될 것이다. 하지만 NP 에 속하는 문제가 모두 다항식으로 해결될 수 있을지 여부를 파악하거나 증명하는 것이 너무나 어렵기 때문에 이 등식은 아직도 완전하게 입증되지 않은 어려운 명제 중의 하나로 통하고 있다.

한편 'NP-hard' 라고 불리는 문제들은 세일즈맨의 여행 문제처럼 모든 경우의 수를 전부 확인해보는 방법 이외에는 정확한 답을 구할 수 있는 뾰족한 수가 없는 문제들을 뜻한다. 어떤 문제가 NP 에 속하면서, 즉 다항식으로 표현될 수 있는지 여부가 알려지지 않았으면서 동시에 NP-hard 에 속한다면 ...... 그 문제는 'NP 완전 문제 (NP-complete)' 라고 부른다. .......

이러한 NP 완전 문제에 속하는 문제는 많다. 비밀번호를 깨뜨리기 위한 해킹 과정도 말하자면 이러한 NP 완전 문제에 속한다고 볼 수 있다. 비밀번호를 찾아내기 위한 알고리즘으로는 세일즈맨의 여행 문제에서 처럼 문자를 하나씩 대입해 보는 것 말고는 다른 뾰족한 방법이 없기 때문이다 ........... (임백준 2003)

SECTION 05 · TERMS, SITES, PAPERS & VIDEOS

관련 용어 · 웹 사이트 · 학술 논문 · 동영상 강의 (원본 보존)

video : 계산 복잡도 이론 주요 강연 및 MIT 공개 강의

P vs. NP and the Computational Complexity Zoo : 2014/08/26
The Turing Computational Model : Juris Hartmanis, Richard Stearns, Stephen Cook, William Kahan : 2013/01/18
Computational Complexity : MIT : Erik Demaine, 2013/01/14