P vs NP 문제는 컴퓨터 과학에서 가장 유명한 미해결 문제로, 클레이 수학연구소가 지정한 밀레니엄 문제 중 하나다. "빠르게 검증할 수 있는 문제는 빠르게 풀 수도 있는가?"라는 질문이 핵심이다.
핵심 정의
P (Polynomial Time):
결정론적 알고리즘으로 다항 시간 내에 풀 수 있는 문제
예: 정렬, 최단 경로, 최대 공약수
NP (Nondeterministic Polynomial Time):
주어진 해답을 다항 시간 내에 검증할 수 있는 문제
예: 부분집합 합, 외판원 문제, SAT
P ⊆ NP (확실)
P = NP? (미해결)
직관적 이해
| 구분 | 문제 예시 | 풀기 | 검증 |
|---|
| P | 소수 판별 | 빠름 | 빠름 |
| NP | SAT | 느림(?) | 빠름 |
| P=NP라면? | SAT | 빠름 | 빠름 |
NP-완전 문제
NP에 속하면서 모든 NP 문제를 다항 시간 내에 환원할 수 있는 문제.
최초의 NP-완전 문제: SAT (쿡-레빈 정리, 1971)
유명한 NP-완전 문제들:
- Boolean Satisfiability (SAT)
- 3-SAT
- 외판원 문제 (TSP, 결정 버전)
- 클릭 문제 (Graph Clique)
- 해밀턴 순환 문제
- 0-1 배낭 문제
- 정점 커버 문제
현재 통설과 영향
대부분 전문가: P ≠ NP (99%이상 추정)
증명 시 파급효과:
P = NP 증명 시:
- RSA/AES 등 현대 암호 붕괴
- 단백질 접힘 등 과학 문제 자동 해결
- AI가 인간 수준 창의력 달성
P ≠ NP 증명 시:
- 현대 암호학의 수학적 근거 확립
- 근사 알고리즘 연구의 중요성 증가
관련 개념
