OpenAI повідомила, що модель ШІ спростувала Гіпотезу про експоненційний час (ETH), поставивши під сумнів припущення, на якому дослідники опиралися протягом 27 років. Модель розробила швидший алгоритм для логічної задачі 3-SAT. Система OpenAI згенерувала доведення на природній мові 16 жовтня. Команда переклала доведення на Lean наступного дня, що дозволило програмному забезпеченню перевірити кожен логічний крок.
Опублікований алгоритм вимагає приблизно 2^(n/√log n) кроків для вхідних даних, що містять n змінних. Цей час виконання нижчий за експоненційну нижню межу, передбачену ETH, але все ще занадто повільний для практичних застосувань. OpenAI попереджає, що для досягнення практичного прискорення необхідні значні додаткові дослідження. Рассел Імпагліаццо та Рамамохан Патурі з UC Сан-Дієго очолять огляд разом з Райаном Вільямсом з MIT. OpenAI не претендує на наукове відкриття, дотримуючись попередньої суперечки, пов’язаної з рівняннями Нав’є-Стокса.
Імпагліаццо та Патурі ввели ETH у 1999 році. Гіпотеза стосується 3-SAT, яка ставить питання, чи можна призначити значення істинно-або-хибно змінним, задовольнивши кожну зв’язану умову. Запропоноване рішення легко перевірити, але кожна додаткова змінна подвоює кількість можливих комбінацій для пошуку. ETH стверджує, що жоден алгоритм не може уникнути експоненційного зростання у найгіршому випадку. OpenAI каже, що сотні статей використовували цю гіпотезу для встановлення обчислювальної складності в теорії графів, обчислювальній біології та базах даних. Акронім ETH не має жодного зв’язку з тікером Ethereum.
Результат не доводить, що P дорівнює NP. Питання P проти NP ставить питання, чи можна швидко розв’язувати всі задачі, розв’язки яких можна швидко перевірити. ETH зробив сильніше твердження, ніж P ≠ NP, тому спростування ETH не вирішує цього ширшого питання. Президент і співзасновник OpenAI Гріг Брокман підкреслив цю різницю через кілька годин після оголошення. Алгоритм не загрожує безпосередньо криптографії, що захищає bitcoin та ethereum. Підписи bitcoin використовують еліптичнокриву криптографію, а алгоритм не розв’язує математичну проблему, що лежить в основі цієї системи.
Скотт Ааронсон, професор комп’ютерних наук у Техаському університеті в Остіні, сказав, що студенти повідомили йому про заявлене спростування. Раніші математичні прориви також спростовували припущення щодо обчислювальних обмежень. Анатолій Карацуба спростував гіпотезу Андрія Колмогорова щодо множення приблизно за тиждень у 1960 році. Волькер Штрассен у 1969 році намагався довести оптимальність стандартного множення матриць, але замість цього відкрив швидший підхід. Зараз машини генерують доведення, які люди потім намагаються зрозуміти. У тому ж випуску також зазначалося про додаткові доведення, що стосуються гармонічного аналізу та фізики частинок.
Криптограф Метью Грин попередив, що ШІ може підірвати математику, що захищає гаманці. Бенджамін Каун, член Експертної ради з ринкової інтелігенції BeInCrypto, стверджував, що розвиток галузей, далеких від фінансів, в кінцевому підсумку може змінити ринки. Досягнення в галузі ШІ все частіше перевіряють припущення про обчислювальну складність, від яких залежать цифрові активи.