OpenAI mengatakan bahwa model AI telah membantah Hipotesis Waktu Eksponensial (ETH), menantang asumsi yang telah digunakan para peneliti selama 27 tahun. Model tersebut mengembangkan algoritma yang lebih cepat untuk masalah logika 3-SAT. Sistem OpenAI menghasilkan bukti dalam bahasa alami pada 16 Oktober. Tim tersebut menerjemahkan bukti tersebut ke dalam Lean pada hari berikutnya, memungkinkan perangkat lunak untuk memeriksa setiap langkah logis.
Algoritma yang diterbitkan membutuhkan sekitar 2^(n/√log n) langkah untuk input yang berisi n variabel. Waktu eksekusi ini lebih cepat dari batas bawah eksponensial yang diprediksi oleh ETH, tetapi masih terlalu lambat untuk aplikasi praktis. OpenAI memperingatkan bahwa penelitian tambahan yang signifikan diperlukan untuk mencapai peningkatan kecepatan yang praktis. Russell Impagliazzo dan Ramamohan Paturi dari UC San Diego akan memimpin tinjauan bersama Ryan Williams dari MIT. OpenAI tidak mengklaim kredit ilmiah atas penemuan ini, mengikuti perselisihan sebelumnya yang melibatkan Navier-Stokes.
Impagliazzo dan Paturi memperkenalkan ETH pada tahun 1999. Hipotesis ini berkaitan dengan 3-SAT, yang menanyakan apakah nilai benar-atau-salah dapat diberikan kepada variabel-variabel sambil memenuhi setiap kondisi yang terhubung. Solusi yang diusulkan mudah diverifikasi, tetapi setiap variabel tambahan menggandakan jumlah kombinasi yang harus dicari. ETH menyatakan bahwa tidak ada algoritma yang dapat menghindari pertumbuhan eksponensial dalam kasus terburuk. OpenAI mengatakan ratusan makalah menggunakan hipotesis ini untuk menetapkan kesulitan komputasi dalam teori graf, biologi komputasi, dan basis data. Akronim ETH tidak memiliki hubungan dengan ticker Ethereum.
Hasil tersebut tidak membuktikan bahwa P sama dengan NP. Pertanyaan P versus NP menanyakan apakah semua masalah yang solusinya dapat diperiksa dengan cepat juga dapat diselesaikan dengan cepat. ETH membuat pernyataan yang lebih kuat daripada P ≠ NP, sehingga membantah ETH tidak menyelesaikan pertanyaan yang lebih luas tersebut. Presiden dan salah satu pendiri OpenAI, Greg Brockman, menekankan perbedaan ini beberapa jam setelah pengumuman. Algoritma tersebut tidak secara langsung mengancam kriptografi yang melindungi Bitcoin atau Ethereum. Tanda tangan Bitcoin menggunakan kriptografi kurva eliptik, dan algoritma tersebut tidak menyelesaikan masalah matematis yang mendasari sistem tersebut.
Scott Aaronson, seorang profesor ilmu komputer di Universitas Texas di Austin, mengatakan bahwa para mahasiswa membawa kabar kepada Aaronson tentang klaim pembatalan tersebut. Terobosan matematis sebelumnya juga telah menggugurkan asumsi tentang batasan komputasi. Anatoly Karatsuba membantah dugaan perkalian Andrey Kolmogorov dalam waktu sekitar satu minggu pada tahun 1960. Volker Strassen berusaha membuktikan optimalitas perkalian matriks standar pada tahun 1969, tetapi justru menemukan pendekatan yang lebih cepat. Mesin sekarang menghasilkan bukti-bukti yang kemudian manusia upayakan untuk memahami. Rilis yang sama juga mengklaim adanya bukti tambahan yang melibatkan analisis harmonik dan fisika partikel.
Kriptografer Matthew Green memperingatkan bahwa AI dapat melemahkan matematika yang melindungi dompet. Benjamin Cowen, anggota Dewan Ahli Intelijen Pasar BeInCrypto, berargumen bahwa perkembangan di disiplin ilmu yang jauh dari keuangan pada akhirnya dapat mengubah pasar. Kemajuan AI semakin menguji asumsi kesulitan komputasi yang menjadi dasar aset digital.