지수시간가설은 난제(np-complete)의 해를 찾는 알고리즘의 하한선을 제시하는 데에 주로 쓰이는 개념인데, 난제급 문제라면 아무리 효율적인 알고리즘을 짜더라도 2^O(n), 즉 지수시간보다 빠르게 풀 수 없음을 못박아두는 가설입니다.
오픈AI에서는 이중 일부의 집합에 대해 지수시간가설이 틀렸음을 증명했다고 주장하고 있는데, 사실이라면 지수시간가설에 기반해 결론을 냈던 수많은 문제들의 최적해가 뒤집힐 수 있는 가능성이 생깁니다. 내가 보고있는게 맞나..
https://x.com/danintheory/status/2114833682469122314?s=20