![[레벨:22]](https://gujoron.com/xe/modules/point/icons/default/22.gif "포인트:45714point (53%), 레벨:22/30"){kind=icon}
이금재.https://namu.wiki/w/P-NP%20%EB%AC%B8%EC%A0%9C 나무위키 "P-NP 문제"
https://youtu.be/nxbufH4JnpA "이상협 PNP문제"
어떤 사이트의 암호를 풀어야 하는 상황이 있습니다. 우리는 먼저 암호에 쓰이는 소스 문자가 뭔지를 알아야 합니다. 알파벳인지 십진수인지 한글인지 등등을 먼저 알아야 한다는 겁니다. 이때 암호가 6자리라면 대강 가능한 암호의 조합 숫자가 나올 겁니다. 이걸 알았다면 우리는 각 자리수에 하나씩 (가령) 알파벳을 넣어보며 문이 열릴 때까지 넣어보기만 하면 됩니다. 총 조합의 개수는 산수 잘하시는 분이 풀어보면 될 거고.
실제로 2차 대전에서 튜링이 독일군의 암호를 해석할 때 가장 어려웠던 점이 암호의 구성소를 알아내는 것이었다죠. 할 수 없이 독일군 유보트를 몰래 털어서 암호책을 훔쳐냈다고. 하여간 조합은 나중 문제입니다.
여기서
NP는 알파벳인지 십진수인지 한글인지를 결정하거나 암호가 몇 자리인지를 알아내는 문제이고
P는 그것을 알 때 가능한 조합의 개수를 찾는 겁니다.
당연히 P는 쉽습니다. 한계가 분명하기 때문입니다. NP는 어렵죠. 무한의 가능성을 가지기 때문입니다.
일상의 문제에서 대상을 가리킬 수만 있으면 문제 풀이는 9부 능선을 넘은 거라고 할 수 있습니다. 대부분 어려운 문제는 일단 대상을 지목할 수도 없기 때문에 어려운 거죠. 확증 편향이 일어나는 이유는 그걸 대충 넘어가려고 그러는 거고. NP와 P의 관계가 이와 같습니다.
수학자들은 P와 NP의 크기가 같은지 다른지를 증명하는데 어려움을 겪는다고 하는데, 이건 그냥 괴델의 불완전성 원리와 같은 맥락으로 해석하면 그만입니다. 다만 계에 대한 언어적 정의가 불분명하므로 기존의 귀류법(반증법)이나 수학적귀납법 위주의 수학 증명 방법으로는 설명하기 어렵다고 하는 것 같네요.
귀류법으로는 계가 정해진 경우만 증명될 수 있습니다. 귀류법의 정의 자체가 "한계는 이미 정해져 있음"을 전제하는 방법이기 때문입니다. 그러므로 NP문제는 귀류법으로 절대 증명될 수 없습니다. NP가 귀류법의 정의를 벗어나는 논의이기 때문입니다.
수학적귀납법도 마찬가지입니다. 귀류법과 마찬가지로 수학적귀납법도 전제가 분명할 때만 사용할 수 있는 방법입니다. 수학적귀납법도 일종의 유사추리(유추)의 방법이므로 계(외부-내부)에 대한 전제없이는 성립할 수 없는 내부의 증명 방법입니다.
즉 NP는 계를 정하는 문제이고, P는 계 내부 원소의 조합이 몇 개인지를 맞추는 문제입니다. 여기서 계를 정하는 즉, 원소의 크기(개수)도 정해집니다. 여기서 계를 정하는 것과 원소의 조합을 정하는 것에 대한 정의가 살짝 헷갈릴 수는 있겠습니다. 우리는 대상을 지목한다고 생각하지만, 사실 계를 지목하는 겁니다.
더 정확하게 말하면 계와 대상을 분리하는 순간 대상을 지목한다는 겁니다. 뭐가 종이인지 그림인지부터 알아내는게 중요하다는 거죠. 일반적인 그림이라면 이걸 알아채는게 문제도 아니겠지만 이우환의 그림이나 현대 예술이라면 관객이나 공간조차도 작품의 일부로 동원되므로 알아차리기가 쉽지 않습니다.
하여간 이게 밀레니엄 난제라는데, 저는 동의할 수 없습니다. 어렵긴 개뿔. 밀레니언 난제, 즉 어려운 문제는 그것을 설명하기가 어려워서 어려운 겁니다. 사실상 밀레니엄 NP인 거죠. 윤곽을 정할 수 있으면 이세상의 모든 문제는 해결 가능합니다. 어려운 문제는 이름만 잘 지어도 풀 수 있습니다. 이름이 곧 가리킴이기 때문입니다.
![[레벨:30]](https://gujoron.com/xe/modules/point/icons/default/30.gif "포인트:723492point, 레벨:30/30"){kind=icon}
김동렬
어려운 수학 이야기는 논외로 치고
풀리는 문제와 답을 아는 문제가 있다면
즉 연역과 귀납으로 치면
풀리는 문제 p는 답을 아는 문제 NP인가?
그렇다.
풀리는 문제를 풀면 답을 안다.
문제를 푼다는 것은 단순화 한다는 것이다.
답을 안다는 것은 단순화 한다는 것이다.
그러므로 단순화 한다는 것은 단순화 한다는 것이다.
즉 풀리는 문제는 답을 아는 문제다.
즉 연역되는 것은 귀납된다.
그렇다면 반대로 귀납되는 것은 연역되는가?
NP는 P인가?
연역되지 않는다.
부분의 합은 전체보다 작기 때문이다.
풀리는 문제는 답을 아는 문제이지만 답을 아는 문제는 풀리는 문제가 아니다.
P는 반드시 NP에 속하지만 NP는 반드시 P에 속하지 않는다.
비밀번호가 있다고 해서 그 비밀번호를 찾을 수 있는 것은 아니다.
비밀번호를 찾을 수 있는 것은 비밀번호가 있다.
귀납되는 것은 연역되는가?
연역되지 않는다.
연역되는 것은 귀납되는가?
귀납된다.
비밀번호를 대칭이라고 치면
연역- 어떤 것은 대칭되는가? 대칭된다.
귀납- 대칭되는 것은 어떤 것인가? 어떤 것이 아니다.
어떤 것을 계라고 하면 대칭은 계의 코어다. 질의 입자다.
즉 질은 입자가 있다. 반드시다.
어떤 입자가 있다면 그것은 질인가? 아니다.
사과 하나가 있다면 그 사과의 절반은 있는가? 있다.
절반이 있다면 그것은 사과인가? 알 수 없다.
사과를 반으로 나눌 수 있지만
어떤 절반을 가지고 나머지가 뭔지 알 수는 없다.
이쪽 절반은 사과인데 저쪽 절반은 밤이나 호박일 수도 있다.
수학적 증명과 별개로 구조론적으로는 NP는 P가 아니다.
필연 속에 우연이 있지만 우연 속에 필연은 없다.
암호를 정할 때는 우연을 암호로 삼으면 된다.
거기에 필연이 없기 때문에 암호를 찾을 수 없다.
컴퓨터가 찾지 못하는 암호는 만들 수 있다.
금고는 금고털이가 열 수 있다.
수렴되기 때문이다.
어떤 둘이 일치될 때 금고는 열린다.
발산되는 것으로 암호를 정하면 알 수 없다.
일치는 있는데 그 어떤 둘은 없다. 발산되기 때문이다.
어떤 것은 반드시 일치되지만
일치되는 것은 반드시 어떤 것은 아니다.
사각형 구리거울을 깨서 둘로 나누어 가졌다가 나중에 맞춰보면 눈금이 맞는다.
도장이 그 원리다.
그런데 어떤 눈금이 둘이 맞았다면 그 거울은 사각거울인가 오각거울인가? 알 수 없다.
사물은 사건보다 작다.
금고는 사물이므로 반드시 열린다.
비밀번호는 사건이므로 열리지 않는다.
즉 비밀번호는 사건 + 액션인 것이다.
부분의 합에는 전체에 있는 액션이 빠져 있다.
전체는 부분의 합+액션이다.
자동차는 자동차 부품의 합+조립순서다.
자물쇠는 열린다.
열리는 것은 자물쇠가 아니다.
우주의 기본은 대칭성이다.
수학은 대칭을 따라가는 것이다.
그러므로 P가 NP면 NP도 P라고 생각하는게 자연스럽지만
정이 아닌 동의 영역에서 대칭은 반드시 비대칭을 수반한다.
우주는 대칭이면서 비대칭이다.
처음에는 NP가 P라는데 수학자의 40퍼센트가 동의했지만
나중에는 숫자가 둘어서 20퍼센트이고 지금은 아마 더 줄었을 것이다.
양자역학이 우주가 대칭이면서 동시에 비대칭이라는 점을 설파하고 있기 때문이다.
자물쇠는 열쇠보다 크다.
자물쇠를 쥐고 열쇠를 찾기는 쉽다.
열쇠를 쥐고 자물쇠를 찾을 수 있을까? 못 찾는다.
열쇠를 시간 속에 숨기는 방법이 있기 때문이다.
공간의 일치는 무조건 찾지만
시간의 일치는 우연이므로 찾을 수 없다.
당신이 죽는 것은 필연이지만 언제 죽는지는 우연이다.