P-NP

컴퓨터 과학에서 어떤 문제가 쉬운지 어려운지, 더 나아가 해결 가능한지 불가능한지를 판단하는 척도가 있다. 

바로 P-NP 문제이다.

 

P-NP

P-NP는 컴퓨터 과학에서 어떤 문제가 쉬운 문제인지 어려운 문제인지, 더 나아가 해결이 가능한지 불가능한지를 판단하는 척도가 되는 개념이다.

결정 문제와 최적화 문제

먼저, 문제의 유형을 이해해야 한다.

결정 문제 (Decision Problemn)

어떤 문제가 주어졌을 때 yes 또는 no로 대답할 수 있는 문제를 말한다.

• "이 배열이 정렬되어 있는가?" → Yes/No
• "이 그래프에서 A에서 B로 가는 경로가 존재하는가?" → Yes/No

 

최적화 문제 (Optimization Problem)

어떤 상황이 주어졌을 때 최적의 해를 찾는 문제이다.

• "배열을 정렬하라"
• "가장 짧은 경로를 찾아라"

 

튜링 머신

문제의 난이도를 이해하려면 튜링 머신이라는 개념을 알아야 한다.

결정론적 튜링 머신

• 문제를 일방향으로 해결 (accept 또는 reject)
• 오늘날의 일반적인 컴퓨터와 동일한 개념

비결정론적 튜링 머신

현재 상태에서 다음 상태로 이동할 때 다음 상태가 여러 개 공존하는 머신이다.

• 현실 세계에는 존재하지 않지만 이론적으로 상상한 개념
• 여러 경우를 동시에 탐색할 수 있는 "분신술"같은 능력
• 결정론적 튜링 머신으로는 오래 걸리는 문제를 빠르게 해결 가능

예를 들어, 미로 찾기 문제에서:

• 결정론적 튜링 머신: 한 길씩 차례대로 시도
• 비결정론적 튜링 머신: 모든 길을 동시에 시도

 

시간 복잡도 분류

분제의 난이도는 시간복잡도로 측정한다.

다항 시간 (Polynomial Time)

입력 크기 n에 대해 다항식으로 표현되는 시간 복잡도 다항 시간에 속하는 것들:

• O(1) - 상수 시간
• O(log n) - 로그 시간
• O(n) - 선형 시간
• O(n²), O(n³) - 다항 시간

다항 시간에 속하지 않는 것들:

• O(2^n) - 지수 시간
• O(n!) - 팩토리얼 시간

다항 시간 알고리즘은 "효율적"이라고 간주되고, 지수 시간 이상은 "비효율적"이라고 간주된다.

 

문제 분류

P 문제 (Polynomial time)

결정론적 튜링 머신을 사용해 다항 시간 내에 답을 구할 수 있는 결정 문제 즉, 일반 컴퓨터로 효율적으로 풀 수 있는 문제이다.

특징

• 상수, 로그, 다항 시간으로 풀 수 있는 "쉬운" 문제
• 현대 컴퓨터로 효율적으로 해결 가능

대표적인 예

• 정렬 (Sorting): O(n log n)
• 이진 탐색 (Binary Search): O(log n)
• 최단 경로 (Dijkstra): O(E log V)

 

NP 문제 (Nondeterministic Polynomial time)

비결정론적 튜링 머신을 사용해 다항 시간 내에 답을 구할 수 있는 결정 문제 즉, "분신술"이 가능한 컴퓨터라면 효율적으로 풀 수 있는 문제이다.

특징

• 해를 찾기는 어렵지만, 주어진 해가 올바른지 검증하는 것은 다항 시간에 가능
• P 문제보다 어려운 문제

예를 들어 스도쿠의 경우 해를 찾기에는 어렵고 오래 걸리지만, 주어진 답이 맞는지 확인하는 것은 쉽고 빠르다.

대표적인 예

• 해밀턴 경로 문제 (결정 버전)
• 외판원 문제 (결정 버전)
• 부분집합 합 문제

 

NP-Hard 문제

모든 NP 문제를 다항 시간 내에 어떤 문제 A로 환원시킬 수 있다면, 그 문제 A를 NP-Hard 문제라고 한다. 

환원(Reductions)이란?

A. n개의 숫자를 오름차순으로 정렬
B. n개의 숫자 중 가장 작은 값 찾기
C. n개의 숫자 중 가장 큰 값 찾기
D. n개의 숫자 중 중간 값 찾기​

→ A를 해결하면 B, C, D가 자동으로 해결됨
→ B, C, D는 모두 A로 환원될 수 있음

특징

• 다른 모든 NP 문제만큼 어렵거나 더 어려운 문제
• 해결 가능한지조차 알려지지 않은 가장 어려운 문제
• NP에 속하지 않을 수도 있음

대표적인 예

• 외판원 문제 (최적화 버전)
• 체스에서 이기는 전략 찾기

 

NP-Complete 문제

NP-Hard이면서 동시에 NP에 속하는 문제 즉, 풀 수 있는 문제 중에서 가장 어려운 문제이다.

특징

• 풀 수 있는 문제 중 가장 어려운 문제
• NP-Complete 문제 하나만 다항 시간에 풀면, 모든 NP 문제를 다항 시간에 풀 수 있음

대표적인 예

• 외판원 문제 (결정 버전): "총 비용이 k 이하인 경로가 존재하는가?"
• 해밀턴 경로 문제 (결정 버전): "모든 정점을 한 번씩만 방문하는 경로가 존재하는가?"
• 부분집합 합 문제: "합이 정확히 k가 되는 부분집합이 존재하는가?"

 

외판원 문제로 보는 차이

같은 외판원 문제도 어떻게 질문하느냐에 따라 분류가 달라진다.

외판원 문제 (최적화 버전)

• 질문: "모든 도시를 방문하는 최소 비용 경로는?"
• 분류: NP-Hard (NP-Complete 아님)
• 이유: 최적해를 찾는 것은 검증보다 더 어려움

외판원 문제 (결정 버전)

• 질문: "비용이 k 이하인 경로가 존재하는가?"
• 분류: NP-Complete
• 이유: 주어진 경로가 조건을 만족하는지 검증은 다항 시간에 가능

 

P vs NP: 밀레니엄 문제

P = NP 인가? 즉, P 집합과 NP 집합이 같은가?

이 문제는 수학계의 7대 밀레니엄 문제 중 하나로, 아직 증명되지 않았다. 이 문제를 해결하면 100만 달러의 상금을 받을 수 있다.

P = NP 라면?

• 모든 NP 문제는 결정론적 튜링 머신(일반 컴퓨터)으로 다항 시간 내에 해결 가능
• 암호화, 최적화 등 많은 분야에 혁명적 변화
• 현재 어렵다고 여겨지는 많은 문제들이 효율적으로 풀림
• 문제: 현재 사용되는 대부분의 암호 시스템이 무용지물이 됨

P ≠ NP라면?

• NP 문제는 결정론적 튜링 머신으로 다항 시간 내에 해결 불가능
• 현재 사용되는 암호화 시스템의 안전성이 이론적으로 보장됨
• 일부 문제는 본질적으로 어려울 수밖에 없음

대부분의 컴퓨터 과학자들은 P ≠ NP일 것이라고 믿고 있지만, 아직 누구도 증명하지 못했다.

 

정리

	설명	난이도
P	다항 시간에 풀 수 있는 문제	쉬운 문제
NP	비결정론적으로 다항 시간에 풀 수 있는 문제	P보다 어려운 문제
NP-Complete	NP이면서 NP-Hard인 문제	풀 수 있는 문제 중 가장 어려운 문제
NP-Hard	모든 NP 문제를 환원할 수 있는 문제	가장 어려운 문제 (풀 수 있는지조차 미지수)

 

P-NP는 컴퓨터 과학에서 문제의 난이도를 분류하는 핵심 개념이다. 
P 문제는 효율적으로 풀 수 있지만, NP-Complete 문제는 현재까지 효율적인 해법이 발견되지 않았다. P = NP인지 아닌지는 여전히 미해결 문제이며, 이를 증명하는 사람은 컴퓨터 과학 역사에 길이 남을 것이다. 

 

실무에서 NP-Complete 문제를 만나면, 정확한 최적해 대신 근사 알고리즘이나 휴리스틱을 사용해 실용적인 해를 찾는 것이 일반적이다.