[일반] p np는 졸라 찝찝한 문제지

[익명(115.91)]

왜 이게 안풀려 ㅅㅂ
이런느낌 아니냐

[익명(115.91)]

당연히 p not np일텐데 왜 안풀리는지가 찝찝하지 풀리면 10년 묵은게 다 내려간다

[익명(77.111)]

난 오히려 어려운게 정상이라고 생각한다. 다항시간 알고리즘이 존재하는건 직접 그걸 construct하면 그만이지만, '존재하지 않는다는'걸 증명하는건 훨씬 어려운 영역이라고 생각함.

[익명(77.111)]

솔직히 그리 좋은 추측인지도 모르겠음. 누구나 생각할법한 natural한 추측이지만, 이런 natural한 추측이 수학의 발전에 있어서 항상 좋게 작용한다고 생각하진 않아서. 그리고 설령 P=NP인걸 누군가 증명한다 하더라도, 좋은 다항시간 알고리즘이 존재하는건 또 별개의 이야기다. 일단 증명이 constructive하지 않으면 다항시간 알고리즘의 존재성은 규명될지라도 어떤 알고리즘인지는 모를수도 있고, 예를 들어서 유명한 NP-complete 문제가 시간복잡도가 N^10000인 알고리즘으로 해결된다고 제시되어도 practical한 관점에서는 지수시간 알고리즘과 아무런 차이가 없음.

[익명(77.111)]

그래서 만약 P=NP인게 증명된다면 어떤 방식으로 증명하는지가 되게 중요할것이고, P != NP인게 증명된다면 그냥 대다수 수학자들의 직관이 맞다는걸 보여줄뿐 아무일도 없겠지..

[익명(39.7)]

유사한게 생각났는데 mathoverflow에서 봤나 don zagier가 말하기를 undecidable인 문제들은 너무 natural에서 무조건 일어날만한 명제들인거라고 한 thread가 잇는데 함 봐봐 링크 걸어줌

[익명(39.7)]

https://mathoverflow.net/questions/27755/knuths-intuition-that-goldbach-might-be-unprovable