OpenAI는 모델 해킹 지수 시간 가설을 발표했습니다
OpenAI는 최근 AI 모델이 컴퓨터 과학에서 20년 이상 사용되어 온 추측 지수 시간 가설, 영어 약칭 ETH를 해결했다고 발표했습니다. 이 가설은 특히 계산하기 어려운 문제들이 얼마나 어려운지를 다루며, 불리언 만족 문제 SAT를 예로 들고 있습니다: 주어진 논리 조건 집합에 대해 모든 조건이 동시에 성립하는 값을 찾을 수 있는지 여부입니다. 문제의 규모가 커질수록 알려진 최선의 방법은 기본적으로 가능한 답을 하나씩 시도하는 것뿐이며, 시간 비용은 규모에 따라 지수적으로 증가합니다. 지수 시간 가설은 이러한 문제들이 본질적으로 크게 가속화될 수 없으며, 진정한 의미의 아지수 시간 효율적인 알고리즘이 존재하지 않는다고 추가로 주장합니다.이 가설은 1999년 제안된 이후 이론 컴퓨터 과학의 중요한 기초가 되어 왔으며, 많은 논문들이 이를 바탕으로 특정 문제들이 어렵다는 것과 특정 알고리즘들이 최적에 가까워졌다는 것을 증명해왔습니다. 만약 지수 시간 가설이 뒤집힌다면, 거의 불가능하다고 여겨지는 많은 문제들이 이론적으로 더 나은 해결책이 존재할 수 있음을 의미합니다. OpenAI는 그들의 모델이 k-SAT 문제의 해의 수를 아지수 시간 내에 정확하게 통계할 수 있는 결정론적 알고리즘을 찾았으며, Lean을 사용하여 형식적으로 검증했다고 주장합니다. 만약 이 결과가 최종적으로 전문가 검토를 견뎌낸다면, 지수 시간 가설에 직접적인 영향을 미칠 것입니다.
