코드를 읽고 설명하면, 합격합니다
이 레슨과 관련된 학습 키워드
알고리즘 — 문제 해결의 체계적 접근 → 문제 해결
여러분, 오늘은 컴퓨터 과학 최대의 미해결 문제, 피 대 {엔피→엔피}를 알아볼게요.
이 문제를 풀면 무려 백만 달러 밀레니엄 상금을 받을 수 있어요.
다이어그램 왼쪽 파란 영역을 보세요. 피 클래스는 다항 시간에 풀 수 있는 문제들이에요.
정렬, 최단 경로, {MST→엠에스티} 같은 것들이 여기 속해요.
이제 빨간 큰 타원, {NP→엔피} 영역을 보세요.
{NP→엔피}는 다항 시간에 검증할 수 있는 문제의 집합이에요.
여기서 핵심 차이를 주목하세요. 풀기와 검증은 완전히 다른 개념이에요.
예를 들어 수독 퍼즐을 생각해 보세요. 풀기는 어렵지만 답이 맞는지 확인은 쉽죠.
그림 가운데 주황색 영역이 {NP-complete→엔피 컴플리트}예요. {NP→엔피}에서 가장 어려운 문제들이죠.
{SAT→샛}, {TSP→티에스피}, 해밀턴 경로 같은 문제들이 여기 있어요.
보라색 점선 밖의 영역은 {NP-hard→엔피 하드}예요. 정지 문제처럼 검증조차 어려운 것들이죠.
이제 아래쪽 핵심 질문을 보세요. 피가 {NP→엔피}와 같은지가 백만 달러짜리 질문이에요.
피가 {NP→엔피}에 포함된다는 건 자명해요. 풀 수 있으면 당연히 검증도 되니까요.
하지만 그 역방향, 검증 가능한 문제를 항상 효율적으로 풀 수 있는지는 아무도 몰라요.
대부분의 전문가는 피와 {NP→엔피}가 다르다고 믿어요. 만약 같다면 암호 체계가 모두 무너지거든요.
이건 단순한 학술 문제가 아니에요. 현대 정보 보안의 기반이 여기에 달려 있어요.
그래서 피가 {NP→엔피}와 다르다는 전제 하에 {근사→어프록시메이션} 알고리즘이 발전했어요.
다음 슬라이드에서 {NP-complete→엔피 컴플리트}의 정확한 정의를 알아볼게요.
이 벤 다이어그램의 구조를 잘 기억해두세요. 계속 나올 핵심 개념이에요.
자, 이 벤 다이어그램 구조를 확실히 이해했다면 다음으로 넘어가 볼까요.