2-5
실패한 증명 시도와 교훈
증명했다는 주장들과 거기서 배울 것.
- 해마다 나오는 「증명했다」 — 그리고 아직 인정된 증명은 없다
P 대 NP 를 풀었다는 주장은 양쪽 방향으로 꾸준히 나온다. Gerhard Woeginger 가 모아 둔 목록을 직접 세어 보고, 그럼에도 학계가 받아들인 증명은 하나도 없다는 사실과, 실패한 시도가 좋은 정리를 낳은 사례를 살핀다.
- 2010년 Deolalikar 의 P ≠ NP 증명 주장 — 공개 검토의 기록
2010년 8월 HP 연구소의 Vinay Deolalikar 가 P ≠ NP 의 증명이라며 원고를 돌리자, 연구자들은 블로그와 위키에서 며칠 만에 공개 검토를 벌였다. 무엇이 주장되었고 어떻게 검토되었으며 어떤 문제가 지적되었는지를 공개 기록에 남은 사실만으로 따라간다.
- 증명 주장을 점검하는 다섯 가지 질문
P ≠ NP 를 증명했다는 글을 볼 때, 그리고 자기 아이디어를 남에게 보이기 전에 던져 볼 질문을 정리한다. 쉬운 문제에서는 왜 안 통하는가, 알려진 알고리즘을 모두 이겨 내는가, 세 장벽을 어디서 넘는가, 알려진 하한을 다시 얻는가, 글이 검증하기 좋게 짜여 있는가.
상태 표시의 뜻
- 검토 중
- 관리자가 읽고 있습니다.
- 보완 필요
- 고칠 것이 있습니다. 무엇인지는 상태 설명에 적혀 있습니다.
- 검토 완료
- 내용을 확인했습니다. 증명이 옳다는 뜻이 아닙니다.
- 주목
- 눈여겨볼 만한 자료입니다.
- 결함 확인
- 알려진 결함이 있습니다. 근거는 상태 설명에 적혀 있습니다.
- 보관
- 더 다루지 않는 자료입니다.