OpenAI math 저장소에 '지수 시간 가설은 거짓' 사전 논문 공개, HN "P=NP는 아니어도 같은 급"

이거 엄청 큰 거 같은데, P=NP는 아니어도 비슷한 급 아닌가? 내가 뭘 놓친 건가.

아니야, 진짜 큼. 10년 전에 사람이 이걸 발표해서 검증까지 됐으면 상 받을 후보였을 거임.

정확히는 P=NP도 아님. 그래도 대단한 성과인 건 맞지.

내가 이해한 바로는 NP가 준지수 시간대에 들어온다는 뜻임. 준지수라고 P=NP는 아니고, 둘 사이 공간은 어마어마하게 넓음.

ETH를 가정하고 결론 낸 논문들 결론이 다 뒤집힐 수 있음. 문제가 쉬워졌다는 게 아니라 예전보다 훨씬 덜 어렵다는 거지.

오히려 P≠NP에 대한 확신이 약해지는 것 같은데, 이쪽 전공자 설명 좀 해줘.

ELI5 하면 3SAT를 준지수 시간에 못 푼다는 게 ETH임. 이름은 좀 이상하게 붙었다고 봄.

3SAT는 변수가 100개면 2^100번 시도하는 게 브루트포스인데, 그보다 빠른 알고리즘이 나왔다는 뜻임. 여전히 어려운 문제일 수 있지만 브루트포스보다 빠르면 큰 진전이지.

P는 다항 시간에 풀 수 있다는 뜻이고 NP는 답을 다항 시간에 검증할 수 있다는 뜻인데, 용어 자체가 사람 헷갈리게 만들어 놓음.

논문이 너무 이해하기 어렵다는 건데, 수학 논문은 원래 수학자한테 쓰는 거고 전공자도 소설 읽듯 안 읽음. 이해 안 되면 넘기면 됨.

수학 전공인데 나도 이 논문은 제대로 못 읽겠음.

그건 그냥 언어 모델이 전문가 안내를 받아서 이 정도까지 나온다는 게 신기한 거임. 결점이 아니라 오히려 우아한 결과 아님?