AI도 못 푸는 문제

내용:

바로 P=NP 문제이다

수학의 밀레니엄 문제 중 하나로 등록되어 있으며

풀면 100만 달러와 함께 전설적인 수학자로 남을 것이다

P 문제와 NP 문제를 간단히 설명하자면

P 문제는 빨리 풀 수 있는 문제고

NP 문제는 빨리 검산할 수 있는 문제다

P⊂NP인건 자명하다

즉 빨리 풀 수 있는 문제는 빨리 검산할 수 있다

근데 NP⊂P인가?

즉 빨리 검산할 수 있는 문제는 빨리 풀 수 있는가?

대부분의 학자는 아니라고 생각한다

증명이 안 되어서 지금까지 삽질을 하고 있지만 말이다

주어진 수가 특정 수의 배수인지 판별하는 문제는 P 문제이다

판별법도 있고, 그냥 나눗셈을 해봐도 그렇게 오래 걸리지는 않기 때문이다

숫자 모음을 오름차순으로 정렬하는 것도 P 문제이다

배스킨라빈스 게임도 P 문제이다

31이 아니라 몇에서 끝내기로 약속하든 필승 전략을 금방 찾을 수 있기 때문이다

(4의 배수 + 1 로 끝나면 후공이 이기고, 그렇지 않으면 선공이 이김)

외판원 문제란

'주어진 모든 도시를 순회할 때, 총 이동 거리를 k 이하로 만드는 경로가 존재하는가?'

이 문제를 빠르게 푸는 방법은 아직도 알려져 있지 않다

도시의 수가 50개만 되어도 슈퍼컴퓨터로 못 풀 정도이다

대신 검산은 빠르게 할 수 있다

경로가 주어지면 총 이동 거리가 k 이하인지 아닌지만 보면 되니까!

따라서 외판원 문제는 NP 문제이다

스도쿠도 NP 문제이다

9×9판이 아니라 일반적인 n×n 판에서 빠르게 푸는 해법이 알려져 있지 않다

하지만 숫자를 전부 채워넣은 답안지를 제공한다면 중복된 숫자가 있는지 확인하는 건 매우 빠르게 할 수 있다

사실 제목은 좀 어그로였지만 틀린 말은 아니다

아직 AI는 약인공지능에 불과하기 때문에 이런 난제를 푸는 것은 불가능하다고 여겨진다

따라서 이런 밀레니엄 문제를 증명하는 건 아직 인간의 몫이라고 할 수 있는 것이다

어쩌면 대 AI 시대에도 인간이 설 자리가 남아있는 게 아닐까?

이상이다