N, NP, NP Complete, NP Hard

P 문제란?

P(Polynomial time) 문제는 입력 크기에 대해 다항식 시간 내에 해결할 수 있는 결정 문제입니다.

정의 : 정답을 빠르게 찾을 수 있고, 그 정답이 맞는지도 빠르게 검사할 수 있는 문제들.

• 여기서 말하는 “빠르게”란 컴퓨터가 문제를 푸는 데 걸리는 시간이 입력 크기의 다항식 시간(예: n, n², n³ 등) 안에 끝나는 걸 말해요.

왜 중요한가?

P 문제는 실제 컴퓨터로 ‘현실적으로 풀 수 있는’ 문제들의 집합이기 때문에 중요합니다.
즉, 알고리즘이 효율적이라는 말과 거의 같다고 봐도 됩니다.

---

NP  문제란?

NP(Nondeterministic Polynomial time)

• Nondeterministic: "비결정적"이라는 뜻. 컴퓨터가 무작위로 정답을 찍을 수 있다고 가정했을 때.
• Polynomial time: 다항식 시간 안에 계산할 수 있다는 뜻. (계산 시간이 n², n³ 등)

정의: 어떤 문제에 대해, '답을 맞게 줬을 때' 그것이 맞는지 '다항식 시간' 안에 검증할 수 있다면 그 문제는 NP에 속한다.

퍼즐 문제: 스도쿠

• 질문: 이 스도쿠 퍼즐이 풀 수 있는 것인가요? (결정 문제)
• 어렵다! 그냥 푸는 건 시간이 오래 걸릴 수 있습니다.
• 그런데 누가 정답을 딱 보여주면, 우리는 금방 검증할 수 있습니다.
  → "숫자가 겹치지 않네, 맞는 해답이야!"

👉 이런 문제가 NP 문제입니다.

---

P,  NP 비교해보기

개념	의미찾기	쉬움?	검증 쉬움?
P 문제	정답을 빠르게 찾고 검증 가능	✔️	✔️
NP 문제	정답은 빠르게 검증 가능하나, 찾는 건 어려울 수 있음	❌	✔️

---

NP  Hard 문제란?

NP-Hard 문제는, 모든 NP 문제보다 최소한 ‘같거나 더 어려운’ 문제들입니다.
그리고 이 문제들을 풀 수 있다면 NP 문제 전부도 풀 수 있게 됩니다.

정의: 어떤 문제 X가 NP-Hard라면, NP에 속한 모든 문제 Y를 다항식 시간 안에 X로 변환(Reduce) 할 수 있어야 해요.

 

즉,

• NP의 모든 문제를 → 이 문제로 변환 할 수 있고,
• 이 문제만 풀 수 있다면 → 모든 NP 문제도 풀 수 있다는 얘기예요.

하지만,

• NP-Hard 문제는 NP에 속하지 않을 수도 있어요 (즉, 검증도 빠르지 않을 수 있음)
• 그래서 NP-Complete보다 더 일반적이고 더 광범위한 개념입니다.

대표적인 NP-Hard 문제 예시

여행하는 외판원 문제 (TSP, Traveling Salesman Problem)

• 문제: 여러 도시를 한 번씩만 방문하고 다시 출발지로 돌아오는 최소 거리 경로는?
• 최적화 버전: “가장 짧은 경로”를 묻는 건 NP-Hard
• 결정 버전: “이 경로가 거리 X 이하인가요?” → 이건 NP-Complete

---

NP-Complete란?

정의 : NP에 속하면서도, NP 안의 모든 문제를 다항식 시간 안에 변환할 수 있는 가장 어려운 문제들.

즉, NP 문제들 중에서도 ‘가장 핵심적인 난이도’에 해당하는 문제들이예요.

---

마무리 요약,

P	빠르게 풀 수 있고 검증도 쉬운 문제
NP	답을 검증하는 건 빠르지만, 푸는 건 어려울 수 있음
NP-Complete	NP 안에 있으면서, 다른 모든 NP 문제를 이 문제로 변환 가능
NP-Hard	NP 문제보다 어려울 수 있는 일반적인 문제 (NP 안일 수도, 아닐 수도 있음)