**P vs NP 문제**는 컴퓨터 과학에서 가장 중요한 미해결 문제 중 하나로, 알고리즘 이론과 복잡도 이론의 핵심 주제입니다. --- ### **P와 NP의 정의** 1. **P (Polynomial Time)** - [[결정적 알고리즘]](Deterministic Algorithm)으로 다항 시간 안에 풀 수 있는 문제의 집합. - 예: 정렬 알고리즘, 두 수의 곱셈, 그래프에서 최단 경로 찾기(다익스트라 알고리즘) 등. 2. **NP (Nondeterministic Polynomial Time)** - 어떤 문제의 "해답을 검증"하는 데 다항 시간 내에 처리할 수 있는 문제의 집합. - 즉, 해답을 주어지면 그것이 맞는지 빠르게 확인할 수 있는 문제들. - 예: 그래프의 해밀턴 순환, 여행 판매원 문제(TSP), 3-SAT 문제 등. --- ### **P vs NP 문제의 본질** - **P 문제는 해답을 찾는 것도 다항 시간 내에 가능**한 문제. - **NP 문제는 해답을 검증하는 것은 다항 시간 내에 가능하지만, 해답을 찾는 것이 다항 시간 안에 가능할지 불분명**한 문제. **P = NP?** - **P = NP**: 모든 NP 문제의 해답을 다항 시간 내에 찾을 수 있다면 성립. - 많은 실질적 문제(암호학, 최적화 등)가 빠르게 풀릴 가능성이 생김. - **P ≠ NP**: 해답 검증은 빠르지만, 해답을 찾는 것은 본질적으로 더 어려운 문제라는 것을 의미. --- ### **예제** - **P 문제**: - 주어진 두 숫자를 더하거나 곱하기. - 그래프에서 최단 경로 찾기. - **NP 문제**: - 어떤 숫자가 큰 소수들의 곱으로 이루어졌는지 확인(소인수 분해). - 특정 그래프에서 해밀턴 순환을 찾기. - 3-SAT(논리식 만족 가능성 문제). --- ### **P vs NP 문제의 중요성** 1. **암호학** - 오늘날 대부분의 암호화 시스템(예: RSA)은 특정 문제가 NP에 속하면서 다항 시간 내에 풀리지 않는다는 가정에 의존. - 만약 P = NP라면, 기존 암호화 시스템은 붕괴. 2. **최적화** - 물류, 공정 최적화, 일정 계획 등에서 많은 문제들이 NP에 속함. - P = NP라면, 이러한 문제를 빠르게 해결할 수 있는 알고리즘이 가능. 3. **과학적 발견과 인공지능** - NP 문제의 빠른 해결은 과학, 공학, 약물 개발 등의 영역에서 혁신을 가져올 수 있음. --- ### **현재까지의 상황** - P와 NP가 같은지 다른지는 아직 증명되지 않았음. - 대부분의 학자들은 **P ≠ NP**일 가능성이 높다고 생각하지만, 이를 증명하거나 반증하는 데 성공한 사람은 없음. - 문제를 풀기 위한 다양한 접근 방식이 시도되었으나, 모두 실패하거나 부분적으로만 진전을 보임.