학술 자료
원 문제가 무엇인지를 다루는 글과 파일. 맨 앞은 Clay 수학연구소의 공식 문제 기술입니다.
- 공식 문제 기술 — Stephen Cook 의 「The P versus NP Problem」(Clay 수학연구소)
Clay 수학연구소가 밀레니엄 문제의 공식 기술로 실은 Stephen Cook 의 글을 절 순서대로 안내한다. 핵심 문장 다섯 곳만 원문과 우리말 옮김을 나란히 싣고, 나머지는 해설이다.
- 형식 정의 — 튜링 기계, 다항 시간, P 와 NP
P 대 NP 문제를 수학 명제로 만드는 정의를 차례로 적는다. 결정 문제와 언어, 결정적 튜링 기계와 시간, P, 두 가지로 정의되는 NP, coNP, 그리고 P ⊆ NP ⊆ PSPACE ⊆ EXP.
- NP-완전성과 Cook–Levin 정리
다항 시간 환산으로 문제의 어려움을 견주는 법, NP-난해와 NP-완전의 정의, SAT 가 NP-완전이라는 Cook–Levin 정리의 뜻과 증명 얼개, Karp 의 21문제, 그리고 P 도 NP-완전도 아닐 수 있는 NP-중간 문제를 설명한다.
- 역사 — 문제는 어떻게 생겨났나
괴델이 폰 노이만에게 보낸 1956년 편지에서 Cobham 과 Edmonds 의 「다항 시간」, Cook·Karp·Levin 의 1971~1973년 논문, 2000년 밀레니엄 문제 지정까지, P 대 NP 문제가 모습을 갖춘 과정을 출처에서 확인한 사실만으로 따라간다.
- 왜 중요한가
P = NP 일 때와 P ≠ NP 일 때 암호, 최적화, 수학 증명 찾기, 기계 학습에서 무엇이 달라지는지를 문헌이 말하는 만큼만 정리한다. P = NP 가 곧 실용적인 알고리즘을 뜻하지는 않는다는 단서와, P ≠ NP 가 암호의 안전을 보장하지는 않는다는 단서를 함께 적는다.
- 흔한 오해
NP 의 뜻, NP-완전과 「풀 수 없음」의 차이, 양자 컴퓨터가 할 수 있다고 알려진 일의 범위, 다항 시간과 지수 시간의 실제 빠르기, SAT 풀이기의 성공과 최악의 경우, 결정 불가능한 문제와의 구분까지 여섯 가지 오해를 문헌에 비추어 바로잡는다.
- P 대 NP 문제의 여러 얼굴 — 같은 물음을 말하는 다른 방법들
P 대 NP 문제를 탐색, NP-완전 문제, 증명 찾기, 논리, 다항 위계, 회로, 증명 복잡도, 대수, 근사의 말로 다시 적어 보고, 각 진술이 P = NP 와 동치인지, 더 강하거나 약한 이웃인지, 닮은꼴일 뿐인지를 가른다.
- 개관 논문 길잡이
P 대 NP 문제를 더 깊이 읽으려는 사람을 위해 Sipser(1992), Fortnow(2009), Aaronson(2017)의 개관 논문과 Wigderson(2019), Arora–Barak(2009)의 책이 각각 무엇을 다루고 누구에게 맞는지, 어디서 읽을 수 있는지를 정리한다.
- P versus NP problem — 문제 정의 (영어 원문)
영어 위키백과 「P versus NP problem」 문서의 서문·예시·정확한 진술의 역사·형식적 정의(P 와 NP) 부분을 CC BY-SA 4.0 에 따라 원문 그대로 옮겨 실은 글이다.
- P 대 NP 문제 — 정의 한글 번역
영어 위키백과 「P versus NP problem」 문서의 서문·예시·역사·형식적 정의를 우리말로 옮긴 글이다. 세부 수식 표기는 영어 원문 글을 기준으로 하고, 흐름 이해를 위해 요지 중심으로 옮겼다.
상태 표시의 뜻
- 검토 중
- 관리자가 읽고 있습니다.
- 보완 필요
- 고칠 것이 있습니다. 무엇인지는 상태 설명에 적혀 있습니다.
- 검토 완료
- 내용을 확인했습니다. 증명이 옳다는 뜻이 아닙니다.
- 주목
- 눈여겨볼 만한 자료입니다.
- 결함 확인
- 알려진 결함이 있습니다. 근거는 상태 설명에 적혀 있습니다.
- 보관
- 더 다루지 않는 자료입니다.