OpenAI стверджує, що спростувала гіпотезу про експоненційний час за допомогою нового алгоритму

ChainCatcher повідомляє, що OpenAI недавно оголосила, що її модель AI розгадала гіпотезу про експоненційний час — математичне припущення, що існувало в комп’ютерних науках понад двадцять років, скорочено ETH, а не Ethereum. Ця гіпотеза стосується того, наскільки складними є особливо складні для обчислення задачі, і використовує задачу булевої задоволеності (SAT) як приклад: чи існує таке присвоєння значень, щоб усі задані логічні умови виконувалися одночасно. Коли розмір задачі збільшується, найкращі відомі методи зводяться до послідовного перебору можливих відповідей, і витрати часу зростають експоненційно з розміром. Гіпотеза про експоненційний час далі стверджує, що такі задачі фундаментально не можуть бути значно прискорені — не існує справжніх ефективних алгоритмів з підекспоненційним часом. З моменту її запровадження у 1999 році ця гіпотеза була важливою основою теоретичної інформатики, і багато наукових праць використовували її для доведення складності певних задач або того, що певні алгоритми майже оптимальні. Якщо гіпотеза про експоненційний час буде спростована, це означатиме, що багато задач, які вважалися майже неможливими для прискорення, теоретично можуть мати кращі розв’язки. OpenAI стверджує, що її модель знайшла детермінований алгоритм, який може точно підрахувати кількість розв’язків задачі k-SAT за підекспоненційний час, і цей результат був формально верифікований за допомогою Lean. Якщо цей результат витримає перевірку експертами, це безпосередньо підкопає гіпотезу про експоненційний час.