AI Study
Cook-Levin 정리와 Karp 21대 문제에서 현대 LLM·GPU 클러스터 최적화까지 — 하나가 풀리면 모두 풀리는 핵심 난제 집합

비결정 완전 : NP-complete

(Non-deterministic Polynomial-time Complete)

NP-완전(NP-complete) 문제는 컴퓨터 과학에서 정답을 빠르게 검증할 수는 있지만, 정답을 직접 찾아내는 데는 엄청난 시간이 걸리는 가장 어려운 문제들의 집합을 말합니다. AI(인공지능) 분야에서 NP-완전은 AI의 한계와 핵심 작동 원리를 결정짓는 매우 중요한 개념입니다.

1. NP-완전의 기본 개념
  • 검증의 용이성 (NP): 누군가 정답을 가져오면, 그 답이 맞는지 틀리는지는 다항 시간(Polynomial time) 내에 빠르게 확인할 수 있습니다. 예를 들어 스도쿠 퍼즐을 직접 푸는 것은 어렵지만, 다 채워진 스도쿠가 규칙에 맞는지 검사하는 것은 매우 쉽습니다.
  • 탐색의 어려움: 데이터의 크기가 조금만 커져도 가능한 모든 경우의 수가 기하급수적으로 늘어납니다. 현재까지 알려진 어떤 알고리즘으로도 현실적인 시간 내에 완벽한 정답을 찾아내기 어렵습니다.
  • 문제 간의 연결성: 모든 NP-완전 문제는 서로 변환이 가능합니다. 즉, 수많은 NP-완전 문제 중 단 하나라도 빠르게 푸는 알고리즘이 발견된다면, 세상의 모든 NP-완전 문제를 빠르게 풀 수 있게 됩니다(P=NP 문제).
2. AI 분야에서 NP-완전이 가지는 의미

AI가 현실 세계의 복잡한 문제를 해결하려고 할 때, 그 문제의 본질이 NP-완전인 경우가 매우 많습니다.

  • 계획 수립 및 추론 (Planning & Reasoning): 로봇이 장애물을 피해 목적지까지 가는 최적의 경로를 짜거나, 논리적 조건들을 만족하는 해답(SAT 문제)을 찾는 과정은 대표적인 NP-완전 문제입니다.
  • 최적화 문제 (Optimization): 물류 배송 경로를 최소화하는 외판원 순회 문제(TSP)나, 한정된 자원으로 최대의 효율을 내는 배낭 문제(Knapsack Problem) 등은 AI가 자주 다루는 최적화 영역이자 NP-완전(또는 그 이상인 NP-난해)에 속합니다.
  • 신경망 학습 (Neural Network Training): 이론적으로 주어진 데이터에 완벽하게 들어맞는 최적의 신경망 가중치를 찾는 문제 역시 NP-완전으로 증명되어 있습니다.
3. AI가 NP-완전 문제를 해결하는 방법

컴퓨터 성능이 아무리 좋아져도 완벽한 답을 찾는 것은 불가능에 가깝기 때문에, AI는 완벽함 대신 실용성을 선택하는 방식으로 발전해 왔습니다.

  • 휴리스틱 (Heuristic): 모든 경우의 수를 다 따져보지 않고, 경험이나 직관에 기반한 '어림짐작' 규칙을 사용해 정답에 가까운 해를 빠르게 찾습니다. (예: A* 길찾기 알고리즘)
  • 근사 알고리즘 (Approximation): 100% 완벽한 최적해는 아니더라도, 수학적으로 오차 범위가 보장된 '충분히 좋은 답'을 빠른 시간 안에 도출합니다.
  • 딥러닝과 확률적 접근: 완벽한 논리적 계산 대신, 방대한 데이터를 학습하여 패턴을 파악하고 확률적으로 가장 그럴듯한 답을 예측합니다. 경사 하강법(Gradient Descent)을 통해 완벽한 전역 최적점(Global Optimum) 대신 쓸만한 지역 최적점(Local Optimum)을 찾는 것이 대표적입니다.

NP-complete(비결정 완전)는 "답을 검증하기는 다항 시간에 쉽지만(NP), 모든 다른 NP 문제를 다항 시간 환원(Reduction)으로 자신에게 번역해 올 수 있을 만큼 가장 어려운(NP-hard)" 문제들의 결정체입니다. AI에서 지식 그래프 매칭, 추론 퍼즐, 제약 충족 계획, GPU 모델 배치, 컴파일러 스케줄링, 심지어 신경망 최적 학습까지 수천 개의 핵심 난제가 이 부류에 연결되어 있습니다.

SECTION 01

AI 관점에서 본 NP-complete 개념과 대표 문제 총정리

성립 조건 ① · NP 소속

답안 검증은 다항 시간(P)에 가능

AI가 어떤 후보 해답(예: 변수 참/거짓 배정표, 외판원 경로, 스도쿠 답안)을 제시했을 때, 그 답이 모든 조건을 만족하는지 컴퓨터가 O(Nk) 다항 시간 내에 오차 없이 검사할 수 있어야 합니다.

성립 조건 ② · NP-hard (다항 환원)

모든 NP 문제가 이 문제로 번역 가능

NP에 속한 그 어떤 문제라도 다항 시간 변환(Reduction)을 거쳐 해당 문제로 바꿀 수 있습니다. 따라서 단 하나의 NP-complete 문제만 빠르게 풀어도 수천 개의 난제가 도미노처럼 한꺼번에 해결됩니다.

대표적인 NP-complete 문제 목록 (고전 컴퓨터과학 & AI 응용 매핑)

① 논리 추론 · 제약 충족
  • Boolean Satisfiability (SAT / 3-SAT): 쿡-레빈 정리 최초의 NP-complete 문제. AI 논리 추론 · 형식 검증(Z3/SMT)의 표준 허브
  • 제약 충족 문제 (CSP): AI 규칙 기반 시스템 · 다중 제약 조건 플래닝
② 그래프 · 지식 표현 · 경로
③ 자원 배분 · ML 학습 · AI 퍼즐
  • 배낭 문제 (Knapsack) & Subset Sum / Bin Packing: 멀티 GPU 모델 샤딩 배치 · 컨텍스트 예산 패킹
  • 소규모 신경망 전역 학습(Blum-Rivest) & 최소 결정 트리 구축: 머신러닝 모델 최적화의 본질적 난이도
  • Fifteen Puzzle (최적 해) · Minesweeper · Tetris · Sudoku: LLM 추론 능력 검증 벤치마크
INFOGRAPHIC 01 · 다항 시간 환원(Reduction) 도미노 & AI 우회 4대 전략 Cook-Levin → Karp 21종 연결 구조와 지수 폭발을 우회하는 AI 방법론
NP-complete : 다항 시간 환원(Reduction) 연쇄 & 지수 시간 우회 4대 해법 "하나의 핵심(SAT)만 정복하면 수천 개 문제가 함께 풀린다 — 그러나 현재 모든 알고리즘은 지수 시간을 요구" 다항 시간 환원(≤ₚ) 사슬 : 모든 NP 문제가 SAT를 거쳐 수천 개 NP-complete 문제로 연결 임의의 모든 NP 문제 (논리 · 제약 · 경로 퍼즐 · 배치 · 계획) 튜링 기계 다항 시간 검증 Cook-Levin SAT (Boolean 충족) 최초의 NP-complete 허브 3-SAT ➔ 논리식 만족 배정 현대 AI 솔버(Z3)의 기준점 Karp 21종 연쇄 환원된 수천 개의 NP-complete 문제들 • Clique · Vertex Cover · Subgraph Isomorphism (지식그래프) • Knapsack · Subset Sum · Bin Packing (GPU/메모리 배치) • Hamiltonian Cycle · TSP · 스도쿠 · 지뢰찾기 · 테트리스 실제 크기의 NP-complete 문제를 다루는 4대 우회 전략 (원전 + 현대 AI 매핑) 1. 근사 (Approximation) 최적해 대비 보장된 비율 내 차선해(Suboptimal) 신속 도출 AI: 양자화 · 근사 어텐션 (PCP 정리: 근사 한계 존재) 2. 확률 (Probabilistic) 실제 입력 분포(Average-case) 에서 빠른 평균 실행시간 달성 AI: SGD 확률적 경사하강법 몬테카를로 트리 탐색(MCTS) 3. 특수 케이스 (Special) 2-SAT, 트리 구조, 평면 그래프 등 제약 조건이 약할 때 다항 해결 AI: 트리형 그래픽 모델(BP) 동적 계획법(DP) · FPT 4. 휴리스틱 (Heuristic) 최악 시간 보장은 없으나 실전에서 "매우 잘 동작하는" 경험적 탐색 AI: LLM + CoT 가설 탐색 CDCL SAT 솔버 분기 예측
SECTION 02 · DEEP RESEARCH

AI와 LLM에서 NP-complete가 중요한 5대 이유

"LLM이 코드를 작성하고 수학을 푸는 시대에 왜 고전 NP-complete 문제들을 알아야 할까?"라는 질문에 대해, Deep Research는 오히려 초거대 AI가 부딪히는 추론 한계, GPU 클러스터 인프라 병목, 솔버 통합 에이전트, 그리고 환각 벤치마크 설계의 모든 중심에 NP-complete가 놓여 있음을 보여줍니다.

심층 분석 01 · 다항 환원과 하이브리드 AI

LLM-Modulo & SAT/SMT 환원: 자연어를 수천 개 난제 해결기로 연결

NP-complete의 핵심 무기인 다항 시간 환원(Reduction)은 LLM 시대에 새로운 날개를 달았습니다. LLM은 수백 개의 제약 조건을 100% 만족하는 일정표나 회로 배치를 텍스트로 직접 암산하는 데는 취약하지만(지수 조합 폭발), 모호한 자연어 요구사항을 SAT(Z3)나 정수 선형 계획법(MILP / OR-Tools) 코드로 번역(Reduce)하는 능력은 매우 뛰어납니다. 즉 "자연어 문제 ➔ LLM 번역(다항 환원) ➔ 산업용 CDCL SAT 솔버 해결" 구조는 LLM의 유연함과 NP-complete 솔버의 완벽한 정합성을 결합한 현대 Neuro-Symbolic AI의 표준 패턴입니다.

심층 분석 02 · 상전이(Phase Transition) 벤치마크

LLM의 진짜 추론력 vs 암기 착시 구분: NP-complete 난이도 경계

대다수 AI 벤치마크는 쉬운 패턴에 치우쳐 있어 LLM이 '추론하는 척' 통계적 지름길만 외워도 높은 점수를 받습니다. 반면 3-SAT에서 절(Clause)과 변수(Variable)의 비율이 약 4.26에 이르는 상전이(Phase Transition) 임계 영역이나 규모가 큰 그래프 색칠 · Subset Sum 인스턴스는 지름길이 통하지 않는 순수한 NP-complete 조합 탐색을 요구합니다. 이 때문에 최근 LLM 추론 연구(예: NP-Bench, 계획 벤치마크)는 NP-complete 문제를 활용해 모델이 진짜 알고리즘적 탐색(CoT Backtracking)을 하는지 아니면 표면 패턴만 암기했는지를 감별합니다.

심층 분석 03 · AI 인프라와 컴파일러

GPU 모델 배치(Bin Packing) & ML 컴파일러 레지스터 할당(Graph Coloring)

초거대 LLM을 수백 대의 H100/B200 GPU에 분산 탑재해 학습·서빙할 때 마주치는 연산 그래프 분할, 텐서/파이프라인 배치, 요청 배치 패킹은 전형적인 Bin Packing 및 Knapsack 문제입니다. 또한 PyTorch torch.compile(TorchInductor), Triton, CUDA 컴파일러가 커널 성능을 극한으로 끌어올리기 위해 수행하는 레지스터 할당(Register Allocation)과 명령어 스케줄링 역시 유명한 NP-complete 문제인 Graph Coloring으로 귀결됩니다. 즉 AI 하드웨어·소프트웨어 스택 전체가 NP-complete 휴리스틱 위에서 돌아갑니다.

심층 분석 04 · 지식 그래프 & 신약 AI

GraphRAG의 Subgraph Isomorphism & 바이오 AI의 결합 탐색

대규모 지식 그래프에서 특정 다중 홉 관계 패턴을 찾아내는 GraphRAG 부분그래프 매칭(Subgraph Isomorphism)과 신약 개발의 분자 골격 탐색·단백질 결합 부위 클리크 매칭(Clique)은 모두 대표적인 NP-complete 그래프 문제입니다. 이 때문에 최신 GraphRAG와 바이오 AI(AlphaFold 계열 / GNN)는 완전 그래프 매칭 대신 임베딩 벡터 근사 검색(ANN) + 빔 서치 + 휴리스틱 가지치기로 지수 폭발을 통제합니다.

심층 분석 05 · 희소성 & 해석가능성 (MCSP / Dictionary Learning)

신경망 내부 회로 해석과 희소 오토인코더(SAE) 최적화

LLM의 뉴런 가중치에서 최소한의 핵심 해석 회로를 분리해 내는 기계적 해석가능성(Mechanistic Interpretability)의 L0 희소 사전 학습(Sparse Coding)이나 최소 크기의 신경/불리언 회로를 찾는 문제는 NP-complete 및 최소 회로 크기 문제(MCSP)와 직결됩니다. 따라서 연구자들은 이산적인 L0 최적화 대신 TopK-SAE나 L1 연속 완화 같은 다항 시간 근사 기법을 통해 LLM 내부 개념을 해독합니다.

INFOGRAPHIC 02 · AI·LLM 전 영역에 스며든 NP-complete 문제와 현대 해법 지도 왜 "LLM 단독 계산"이 실패하는 영역에서 "환원 + 솔버/근사"가 승리하는지 비교
AI · LLM 스택 전 영역에 포진한 NP-complete 난제와 돌파 전략 추론(SAT) · 인프라(Bin Packing) · 그래프(Subgraph) · 해석가능성(Sparse L₀) 모두 NP-complete의 지배를 받는다 ① LLM 추론 에이전트 : LLM-to-SAT/MILP 환원 • 난제: 다중 제약 일정 · TSP 경로 · 스도쿠 · 논리 퍼즐 • LLM 1-Pass 실패 이유: TC⁰ 한계로 지수 조합 분기 추적 불가 해법 ➔ LLM이 자연어를 SAT/MILP 식으로 번역(환원) ➔ Z3 · OR-Tools · CDCL 솔버가 무오류 해답 반환 (Neuro-Symbolic) ② AI 인프라 · GPU 컴파일러 : Packing & Coloring • 난제: GPU 클러스터 모델 샤딩(Bin Packing) & 레지스터(Coloring) • 규모: 수만 토큰 KV 캐시 · 수천 GPU 노드 최적 배치 해법 ➔ 탐욕적 근사 휴리스틱 + PagedAttention 블록화 ➔ Triton/LLVM 그래프 컬러링 휴리스틱으로 GPU 처리량 극대화 ③ GraphRAG · 바이오 AI : Subgraph & Clique • 난제: 대규모 지식 그래프 구조 매칭(Subgraph Isomorphism) • 바이오 AI: 분자 도킹 · 단백질 구조 최소 에너지 탐색 해법 ➔ 그래프 신경망(GNN) · 벡터 임베딩 ANN 근사 탐색 ➔ 확률적 확산(Diffusion) + 에너지 기반 휴리스틱 가지치기 ④ AI 평가 & 해석가능성 : 상전이 & 희소 복원 • 난제: LLM 암기 착시 검증 & 뉴런 희소 개념(L₀) 분해 • 특징: 3-SAT 상전이(4.26 비율) 경계에서 진짜 추론력 판별 해법 ➔ NP-Bench 난이도 계층 평가 + TopK/L₁ SAE 근사 ➔ 이산 NP 조합을 미분 가능 연속 공간으로 완화해 해석·학습
SECTION 03 · FOR AI ENGINEERS

AI 개발자들에게 NP-complete가 가지는 5대 실무 의미

현업 AI 개발자에게 NP-complete는 "절대 못 푸니 포기하라"는 사망 선고가 아닙니다. 오히려 "수천 개 난제가 하나의 SAT·솔버 허브로 환원된다는 축복"이자 "LLM 텍스트 추론에 맡길 문제와 전용 알고리즘·휴리스틱으로 풀 문제를 가르는 기준"입니다.

실무 의미 01

다항 환원(Reduction) 사고로 도구 연결

복잡한 근무표 배정, 클라우드 비용 최적화, 의존성 그래프 충돌 해결이 들어올 때 LLM에게 답을 직접 찍게 하지 마세요. LLM으로 요구사항을 SAT(Z3) 또는 OR-Tools 제약 모델로 환원(변환)시키는 에이전트를 만들면 완벽한 해답을 얻습니다.

실무 의미 02

4대 우회 무기(근사·확률·특수·휴리스틱) 선택

문제가 NP-complete임을 간파하는 순간 개발자는 100% 정확도에 매달려 타임아웃을 맞지 않고, 근사 알고리즘 · 확률적 평균 해법 · 그래프 트리 같은 특수 케이스(DP) · LLM 가설 휴리스틱 중 최적의 타협안을 즉시 선택합니다.

실무 의미 03

서빙 인프라 & 컨텍스트 패킹 최적화

제한된 토큰 예산(Context Window) 안에 가장 가치 있는 RAG 청크만 골라 담는 작업은 배낭 문제(Knapsack), 여러 모델 인스턴스를 GPU VRAM에 얹는 작업은 빈 패킹(Bin Packing)입니다. 도메인 지식으로 좋은 패킹 휴리스틱을 짜는 것이 곧 성능입니다.

실무 의미 04

"작은 테스트 성공 ➔ 대규모 붕괴" 조기 경고

노드 5개짜리 경로/일정 데모에서는 GPT/Claude가 완벽해 보이지만 노드 30개가 되면 230 조합 폭발로 환각을 일으킵니다. 문제 본질이 NP-complete임을 알면 데모 단계에서부터 아키텍처를 분리할 수 있습니다.

실무 의미 05

검증 가능한 보상(RLVR)을 위한 문제 재정의 역량

NP-complete의 정의처럼 "후보 답안의 정합성 검증만큼은 무조건 다항 시간(P)에 100% 정확히 가능하다"는 성질은 최고의 무기입니다. AI 개발자가 LLM 출력을 다항 시간 검증기로 즉시 채점하고 피드백하는 루프를 붙이면, 어려운 탐색 문제를 신뢰성 있는 AI 프로덕트로 바꿀 수 있습니다.

SECTION 04 · ARCHIVE & EULER DIAGRAM

원전 해설 및 P · NP · NP-complete · NP-hard Euler Diagram

EULER DIAGRAM · P · NP · NP-complete · NP-hard 문제 부류의 포함관계 P ≠ NP 가정(좌) 및 P = NP 가정(우)에서의 정확한 집합 포함관계 비교
Euler Diagram : P · NP · NP-complete · NP-hard 포함관계 핵심 관계식 : P ⊆ NP | NP-complete = NP ∩ NP-hard | NP-hard는 NP 바깥 영역까지 포함 현실적 정설 : P ≠ NP 인 경우 NP-hard (NP 난해) NP 바깥 영역 (검증조차 다항 시간 아님 / 결정 불가) • 정지 문제(Halting) · TSP 최적화 · QBF(PSPACE) • LLM 최적 양자화 · 베이지안 정확 추론(#P-hard) NP-complete (NP ∩ NP-hard) SAT · Knapsack · TSP 결정판 · 해밀턴 사이클 · Clique NP (다항 시간 내 해답 검증 가능) (예: 소인수분해 등 P와 NP-complete 사이 영역 포함) P (다항 시간 해결) 정렬 · 최단경로(Dijkstra) · 순전파 P ⊂ NP 이며 NP-complete와 분리됨 가정된 경우 : P = NP 인 경우 NP-hard (NP 난해) NP 바깥의 초월·결정불가 문제는 여전히 남음 • 정지 문제(Halting Problem)는 P = NP가 증명되더라도 여전히 결정 불가능함! P = NP = NP-complete 모든 NP-complete 문제가 다항 시간으로 붕괴 SAT · TSP · 배낭 · 스도쿠가 P 시간 내 해결! (단, NP ∖ 결정가능 영역의 NP-hard는 여전히 다항 시간 해결 보장 안 됨)

계산 복잡도 이론 (Computational Complexity Theory) 에서, NP-complete 문제는 NP 중에서 가장 어려운 문제들이다 (그것들이 대부분 P 에는 속하지 않는다는 점에서). 그 이유는 만일 어떤 NP-complete 문제를 빨리 푸는 방법을 발견할 수 있다면, 모든 NP 문제들을 빨리 푸는데 그 알고리즘을 사용할 수 있기 때문이다. .........

현재 NP-complete 문제를 위한 모든 알려진 알고리즘들은 문제의 크기에서 지수적인 (exponential) 시간을 요구한다. 어떤 더 빠른 알고리즘이 있는지는 모른다. 그러므로 어떤 명백하지 않은 (non-trivial) 문제 크기의 NP-complete 를 해결하기 위해서, 다음과 같은 접근 방법중의 하나가 사용된다.

  • 근사 (Approximation) : 어떤 알려져 있는 적절한 범위내에 있는 차선의 (suboptimal) 해결책을 빠르게 찾는 알고리즘. 모든 NP-complete 문제가 good approximation algorithms 을 가진 것은 아니며, good approximation algorithm 을 발견한 문제도 문제 그 자체를 해결하기에 충분하지는 않다.
  • 확률 (Probabilistic) : 문제의 instance 에 대한 확률 분포 (이상적으로는 "hard" 입력에 대해 낮은 확률을 할당하는) 에 대해 훌륭한 평균 runtime behavior 를 낳는다고 입증된 알고리즘
  • Special cases : 문제의 instance 가 어떤 특별한 경우에 속한다면 빠르다는 것이 입증된 알고리즘
  • 휴리스틱 (Heuristic) : 많은 경우에 "reasonably well" 작동하지만, 항상 빠르다는 증명은 없는 알고리즘

어떤 새로운 문제가 NP-complete 하다는 것을 증명하는 가장 쉬운 방법은, 이미 알려진 NP-complete 문제를 그것으로 환원하는 (reduce) 것이다. 그러므로 다양한 NP-complete 문제를 아는 것은 유익하다. 다음은 그중 일부이다.

다음 그림은 NP-complete 문제와 그들 사이의 상대적인 위치를 보여주는 그림이다. ......... (Wikipedia : NP-complete)

Stephen Cook 은 .... 1971 년 컴퓨팅의 이론을 주제로 열린 ACM (컴퓨팅 기계 협회) 의 제 3 차 연례 심포지엄에서 발표할 논문에서 .... 가능한 해법, 즉 '후보' 해법이 다항식 시간 내에 검토될 수 있는 문제들을 다루었다........ 어떤 프로그램은 그 해법을 추측해야만 하는 경우도 있다. 이러한 이유에서 쿡은 그 문제들에 비결정 다항식 (nondetermnistic polynomial) 혹은 NP 문제라는 이름을 붙였다. 추측 부분은 비결정적이고 검사 부분은 다항식이라는 의미이다. 세일즈맨의 여행 문제와 만족성 문제는 양자 모두 이러한 속성을 가진다. 여행 계획의 어떤 후보가 그 세일즈맨의 예산을 충족시키는지, 혹은 어떤 진리값 지정의 후보가 참인 공식을 만들어 낼 것인지를 빠른 시간 내에 적당한 후보를 찾아 내는 것이 과연 가능한가하는 것이다........

쿡의 논문이 발표되고 얼마 안 있어, UC 버클리의 Richard Karp 가 또 다른 21 가지 문제가 NP-완전임을 보여 주었다. 그 중엔 세일즈맨의 여행 문제와 긴밀하게 연관된 문제도 포함되어 있었다. ....... 카프의 연구 이후 세계 각지의 연구자들은 수천 가지의 문제가 NP-완전임을 보여 주었다. 전형적인 예는 전화망의 최적 기하학적 레이아웃, 또는 체커같은 게임을 하는 가장 좋은 방법 등이다. 쿡은 NP-완전 문제의 수에 당황하였다. "난 그저 NP-완전이 흥미로운 발상이라고만 생각하였습니다. 그것의 잠재적 영향력은 제대로 인식하지 못했던 것이지요." ...........

어떤 문제가 어느 정도의 시간 내에 해결될 수 있다면, 그것의 해법은 그 시간 내에 검토될 수 있다. 따라서, P 는 NP 내에 포함된다. 컴퓨터 과학에서 아직 미해결 상태인 이론상의 한 가지 큰 문제는, NP-완전에 속하는 천 가지 중요한 문제들이 실제로 다항식 시간 내에 해결될 수 있는지 아니면 지수 시간을 필요로 하는지 여부이다. 다시 말해, P 가 NP 와 일치하는가의 문제인 것이다.

스티븐 쿡 : 이 분야의 수학이 처해 있는 슬픈 상황은 우리가 이것들을 증명할 수 없다는 것입니다. 우리는 P 가 NP 와 일치하지 않는다는 것을 증명할 수가 없습니다. 따라서, 결국엔 누군가가 NP-완전 문제를 다항식 시간 내에 해결할 어떤 명쾌한 병렬 알고리즘을 고안해 낼 수 있을 것입니다. .... 사람들은 각기 다른 수많은 영역에서 그 문제를 공략하고 있습니다. 그리고 어찌되었든 P = NP 가 되는 것은 가능합니다. ........... (Dennis Shasha 1995)

SECTION 05 · TERMS, SITES, PAPERS & VIDEOS

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

site :

video : NP-complete 및 P vs NP 주요 대학·석학 강의

P vs. NP and the Computational Compelxity Zoo : hackerdashery : 2014/08/26
The "P vs. NP" Problem : ETH Zurich : Avi Widgerson, 2012/05/07
23. Computational Complexity : MIT OCW : Erik Demaine, 2012/01/14 ... Playlist 47
NP Completeness∥& Reductions - Lecture 16 : Coderisland : Shai Simonson, 2012/19/31 .... Playlist 19