오픈AI에서 지수시간가설(Expoential Time Hypothesis)이 거짓임을 증명하고, 이를 Lean으로 검증까지 마쳤다고 공개해 수학/컴공학계에 충격을 주고있습니다.

지수시간가설은 난제(np-complete)의 해를 찾는 알고리즘의 하한선을 제시하는 데에 주로 쓰이는 개념인데, 난제급 문제라면 아무리 효율적인 알고리즘을 짜더라도 2^O(n), 즉 지수시간보다 빠르게 풀 수 없음을 못박아두는 가설입니다.

오픈AI에서는 이중 일부의 집합에 대해 지수시간가설이 틀렸음을 증명했다고 주장하고 있는데, 사실이라면 지수시간가설에 기반해 결론을 냈던 수많은 문제들의 최적해가 뒤집힐 수 있는 가능성이 생깁니다. 내가 보고있는게 맞나..