CampusDownWiki
누적 인용 126,015한국어KO 12,862EnglishEN 77,490日本語JA 9,775中文ZH 25,888
캠퍼스다운 홈 ↗
한국어

P 대 NP 문제

➗ 수학·통계 작성 캠퍼스다운 위키 편집부 최종 수정 조회 1
P 대 NP 문제는 컴퓨터 과학의 가장 큰 미해결 질문 중 하나예요. 제시된 답이 맞는지 빨리 확인할 수 있다면, 그 문제를 빨리 풀 수도 있을까요? 클레이 수학연구소의 7대 밀레니엄 문제 중 하나예요.
목차
  1. 1. 기숙사 배정 예시
  2. 2. P와 NP는 무슨 뜻일까
  3. 3. 100만 달러짜리 질문
  4. 4. 자주 묻는 질문
  5. 5. 참고문헌

1,000조각 직소 퍼즐을 맞추는 데는 몇 시간이 걸려요. 다른 사람이 다 맞춘 걸 확인하는 데는 몇 초면 돼요. 이 차이는 진짜일까요, 아니면 아직 똑똑한 방법을 못 찾았을 뿐일까요? 그게 P 대 NP 문제예요.

한 학생은 흩어진 직소 퍼즐 앞에서 인상을 쓰고, 다른 학생은 완성된 퍼즐을 돋보기로 차분히 확인하는 그림
풀기는 어렵고 확인은 금방이에요. 정말 다른 걸까요?

기숙사 배정 예시

클레이 수학연구소는 이렇게 설명해요. 학생은 400명인데 기숙사 자리는 100개뿐이고, 학장이 함께 살면 안 되는 학생 짝 목록을 줘요. 누가 만든 100명 명단을 확인하는 건 쉬워요. 금지된 짝이 없는지만 보면 되니까요. 하지만 그런 명단을 처음부터 찾는 건 달라요. 400명 중 100명을 고르는 방법의 수가 알려진 우주의 원자 수보다 많아서, 컴퓨터로 하나씩 다 따져 볼 수도 없어요.

P와 NP는 무슨 뜻일까

P와 NP 비교: P는 정렬처럼 빨리 풀 수 있는 문제, NP는 완성된 스도쿠나 함께 살 수 있는 룸메이트 명단처럼 답을 받으면 빨리 확인할 수 있는 문제
빨리 풀기 vs 빨리 확인하기.

P는 컴퓨터가 빨리 풀 수 있는 문제들이에요. NP는 제시된 답을 빨리 확인할 수 있는 문제들이에요. 클레이 연구소는 P를 '찾기 쉬움', NP를 '확인하기 쉬움'이라고 줄여 말해요.

핵심 질문은 이거예요. 확인하기 쉬운 문제는 사실 모두 풀기도 쉬울까요? 그렇다면 P = NP예요. 대부분의 연구자는 아니라고 짐작하지만, 어느 쪽도 증명한 사람은 없어요.

100만 달러짜리 질문

스티븐 쿡과 레오니드 레빈이 1971년 각자 이 문제를 정식화했어요. 클레이 연구소는 2000년 이 문제를 7대 밀레니엄 문제 중 하나로 정하고 문제마다 100만 달러를 걸었어요. 지금까지 풀린 건 푸앵카레 추측 하나뿐이에요.

자주 묻는 질문

NP는 무슨 뜻이에요?
비결정적 다항 시간(Nondeterministic Polynomial time)의 약자예요. 쉽게 말해 답을 빨리 확인할 수 있다는 뜻이에요.
누가 풀었나요?
아직 아무도 못 풀었고, 클레이 상금도 그대로 남아 있어요.
왜 중요해요?
일정 짜기, 경로 찾기, 보안 같은 어려운 문제들에 빠른 해법이 있는지가 걸려 있어요.

참고문헌

  1. Clay Mathematics Institute. P vs NP. 공식 문제 소개: 확인은 쉬운데 풀기도 쉬울까, 기숙사 배정 예시, 1971년 쿡과 레빈.
  2. Clay Mathematics Institute. The Millennium Prize Problems. 2000년 지정된 7문제, 문제당 100만 달러, 푸앵카레 추측만 해결.

이 글이 도움이 됐다면 친구에게 공유해 주세요

필요한 친구에게 한 번에 보내 보세요. 공유는 큰 힘이 돼요.

X Facebook 스레드

이 이론으로 쓴 레포트·자료

아직 이 이론만 따로 다룬 자료는 없지만, 캠퍼스다운 자료실에서 관련 레포트를 검색해 볼 수 있어요.

레포트 더 찾기 · 'P 대 NP 문제' 검색 결과 보기 →

같이 보면 좋은 이론

최신 아티클전체보기 ›

대학생 공부·과제에 바로 쓰는 새 정보 글

이 문서는 2026년 11월 20일에 마지막으로 수정되었습니다. 내용은 널리 알려진 원전과 교과서를 바탕으로 정리했으며, 레포트에 인용할 때는 아래 참고문헌의 원전을 직접 확인하세요.