HYPSVC 서비스 4
★ 본사 직영 서비스
무료 이용

P vs NP 문제 풀기

컴퓨터과학 최대 난제인 P vs NP 문제를 읽고, 직접 풀어 보고, 풀이 아이디어를 함께 쌓아 가는 연구 서비스입니다. Clay 수학연구소 공식 문제 기술의 길잡이부터 지금까지의 증명 노력, 퍼즐 체험, 도전 아이디어까지 한곳에 모았습니다. 가입 없이 누구나 읽고 퍼즐을 풀 수 있고, 글이나 파일로 참여할 때만 무료 패스를 받으면 됩니다.

밀레니엄 난제 P vs NP 를 누구나 가입 없이 읽고 직접 풀어 보는 공개 연구 서비스입니다. 공식 문제 기술의 해설, 지금까지의 증명 노력, 퍼즐 체험, 도전 아이디어와 지도, 개념 사전, 참고문헌을 한곳에 모았습니다. 글과 파일을 올려 참여하려면 무료 패스를 받으면 됩니다.

가입 없이 바로 둘러보기 →글을 쓰려면 — 무료 패스 받기 서비스 커뮤니티

가입하지 않아도 자료를 읽고 퍼즐을 풀 수 있습니다. 글이나 파일을 올리려 할 때만 로그인과 무료 패스(약관 동의)가 필요합니다.

3분 체험

답을 확인하기 쉬운 문제는, 답을 찾기도 쉬울까요?

P vs NP 문제를 한 줄로 줄이면 이 질문입니다. 어렵게 들리지만, 색칠 놀이 하나로 바로 느껴 볼 수 있어요.

퍼즐 화면의 첫 문제 그대로입니다 — 점 6개 가운데 3개를 미리 칠해 두었어요. 나머지를 칠해 보세요.

규칙은 하나 — 선으로 이어진 두 점은 서로 다른 색이어야 해요. 색은 주황 · 초록 · 파랑 세 가지뿐입니다.
확인은 금방 — 다 칠한 그림이 맞는지는 선을 하나씩 훑어보면 바로 알 수 있어요.
찾기는 막막 — 그런데 맞게 칠하는 방법을 처음부터 찾는 건 점이 늘수록 급격히 어려워집니다.

칠하는 방법을 하나씩 다 해 본다면 — 1초에 10억 가지씩
점	칠하는 방법	다 해 보는 시간
6개	729가지	0.001초 미만
30개	약 2.06×10¹⁴가지	약 2일
100개	약 5.15×10⁴⁷가지	약 1.6×10³¹년 (우주 나이의 약 1.2×10²¹배)

확인은 쉬운데 찾기는 어려워 보이는 문제를 언제나 빨리 푸는 방법이 있을까요? 아직 아무도 모릅니다. 이것이 P vs NP 문제이고, 풀면 상금 100만 달러가 걸린 밀레니엄 문제입니다.

직접 칠해 보기 → 다른 퍼즐도 있어요: SAT 부분합

그림으로 둘러보기

반세기 넘게 이어진 도전, 그림으로 먼저 만나 보세요

서비스 안의 글에는 직접 그린 도식이 곳곳에 있습니다. 그림을 누르면 그 글이 실린 곳으로 가요 — 읽기도 가입 없이 됩니다.

1960년부터 2010년까지의 시간 축 위에 세 쌍의 화살표가 있다. 대각선 논법의 성공(1965)에서 상대화(1975)로, 회로 하한의 성공(1981–1987)에서 자연 증명(1994)으로, 산술화의 성공(1990)에서 대수화(2008)로 이어진다.

2장 · 연표 성공 뒤에 장벽이 왔다 대각선 논법 · 회로 하한 · 산술화 — 기법마다 큰 성공을 거둔 뒤, 몇 년 지나 「이 방법만으로는 P vs NP 를 풀 수 없다」는 장벽이 증명됐습니다. 1960년부터 2010년까지의 흐름을 한 장에 담았어요. 「연표」 읽으러 가기 →

기법과 장벽의 격자. 논리적 기법은 상대화에 걸리고 자연 증명은 피한다. 조합적 기법은 상대화를 피하고 자연 증명에 걸린다. 산술화 기반 기법은 상대화와 자연 증명을 피하고 대수화에 걸린다. Williams 의 NEXP ⊄ ACC⁰ 는 세 장벽을 모두 피한 것으로 평가된다.

2장 · 세 장벽 세 장벽이 막는 기법 상대화 · 자연 증명 · 대수화 — 지금까지의 증명 기법이 왜 끝까지 가지 못하는지 보여 주는 세 개의 벽입니다. 어떤 기법이 어느 벽에 걸리는지 격자 한 장으로 보고, 세 벽을 모두 피했다고 평가되는 결과도 만나 보세요. 「세 장벽」 읽으러 가기 →

지금 할 수 있는 것

읽기와 퍼즐은 가입 없이, 쓰기는 무료 패스로 합니다. 아래는 지금 서비스에서 할 수 있는 것입니다.

직접 풀어 보는 퍼즐 3종

SAT · 그래프 3색칠 · 부분합 퍼즐을 화면에서 직접 풉니다. 답이 맞는지 확인하는 것은 한순간인데 답을 찾는 것은 크기가 커질수록 막막해지는 것을 손으로 겪어 봅니다. 크기를 키우면 경우의 수가 얼마나 불어나는지 함께 보여 주고, 컴퓨터에게 전부 해 보게 할 수도 있습니다.

공식 문제 기술과 학술 자료

Clay 수학연구소의 공식 문제 기술 원문으로 가는 링크와 우리말 길잡이를 맨 앞에 두고, 형식 정의 · NP-완전성 · 역사 · 흔한 오해처럼 문제 자체가 무엇인지를 다루는 글을 모았습니다.

지금까지의 증명 노력

연표 · 세 장벽(상대화 · 자연 증명 · 대수화) · 주요 접근 · 알려진 부분 결과 · 실패한 증명 시도와 교훈 · 전문가들의 견해를 절별로 읽습니다.

도전 아이디어와 하위 정보

풀이 아이디어를 개요 → 구체적 진행 방법 → 왜 해볼 만한가 3단으로 읽습니다. 아이디어마다 댓글 대신 질의 · 보완 · 반론 · 자료를 하위 정보로 덧붙여 생각을 이어 갑니다.

아이디어 지도

도전 아이디어를 접근 분야 × 넘어야 할 장벽 격자에 놓고 봅니다. 어느 칸이 붐비고 어느 칸이 비어 있는지 한눈에 보입니다.

개념 사전 · 참고문헌 카드

글을 읽다 막히는 용어는 개념 사전에서 뜻을 찾습니다. 참고문헌 카드는 모아 보고 검색할 수 있고, 카드마다 원문을 직접 확인했는지가 표시됩니다. 글을 쓸 때 카드를 골라 붙입니다.

자료 더하기 — 글 · 파일

무료 패스를 받으면 자료와 하위 정보를 올립니다. 작성기(3단 칸을 채우는 방식) · 단순 글 · 파일 올리기(PDF · 원고 · 그림 등, 한 자료에 여러 개) 가운데 골라 쓰고, 내 글은 언제든 고치거나 지울 수 있습니다.

검토 상태 · 추천 · 신고

관리자가 자료마다 검토 상태(검토 중 · 보완 필요 · 검토 완료 · 주목 등)를 달고 설명을 남깁니다 — 「검토 완료」도 증명이 옳다는 뜻은 아닙니다. 회원은 추천하고, 부적절한 글은 신고합니다. 신고가 쌓이면 자동으로 숨겨집니다.

이용 순서

1단계 가입 없이 둘러보기

「가입 없이 바로 둘러보기」를 누르면 로그인 없이 실행 화면이 열립니다.
2단계 퍼즐로 직접 풀어 보기

SAT · 그래프 3색칠 · 부분합 가운데 골라, 확인은 쉽고 찾기는 어려운 것을 직접 겪어 봅니다.
3단계 자료와 아이디어 읽기

공식 문제 기술의 길잡이, 지금까지의 증명 노력, 도전 아이디어와 지도를 읽습니다.
4단계 쓰고 싶을 때만 무료 가입

글이나 파일을 올리려 할 때 로그인(회원가입)하고, 그 자리에서 무료 패스와 약관 동의를 한 번에 끝냅니다.
구독 · 패스 안내

이용 패스 비교

자료 읽기와 퍼즐은 패스 없이 됩니다. 패스는 글 · 파일 올리기와 추천 · 신고에 필요합니다.

이 서비스는 현재 무료 패스만 제공합니다 — 유료 등급은 아직 없습니다. 유료 등급이 등록되면 이 자리에 자동으로 함께 나타납니다.

무료 패스