OpenAI Mengaku Membantah Hipotesis Masa Eksponen dengan Algoritma Baharu

Mesej ChainCatcher, OpenAI baru-baru ini mengumumkan bahawa model AI-nya telah memecahkan hipotesis masa eksponen yang telah digunakan selama dua dekad dalam ilmu komputer, singkatan bahasa Inggeris ETH, bukan Ethereum. Hipotesis ini memfokuskan pada seberapa sukar masalah yang sangat sukar dihitung, dengan menggunakan masalah kepuasan Boolean SAT sebagai contoh: diberikan satu set syarat logik, adakah terdapat satu penugasan yang membuat semua syarat berlaku serentak? Apabila skala masalah bertambah, kaedah terbaik yang diketahui hampir pasti hanya boleh mencuba setiap jawapan secara berurutan, dengan kos masa yang meningkat secara eksponen mengikut skala. Hipotesis masa eksponen selanjutnya menyatakan bahawa masalah-masalah ini secara asas tidak boleh dipercepatkan secara besar-besaran, dan tiada algoritma efisien masa sub-eksponen yang benar-benar wujud. Sejak diperkenalkan pada tahun 1999, hipotesis ini telah menjadi batu asas penting dalam ilmu komputer teori, dengan banyak kertas kerja menggunakannya untuk membuktikan bahawa sesetengah masalah sukar atau sesetengah algoritma hampir optimal. Jika hipotesis masa eksponen dibantah, ia bermakna ramai masalah yang dianggap hampir mustahil untuk dipercepatkan mungkin secara teori mempunyai penyelesaian yang lebih baik. OpenAI menyatakan bahawa modelnya telah menemui algoritma deterministik yang mampu mengira jumlah penyelesaian untuk masalah k-SAT dalam masa sub-eksponen, dan telah disahkan secara formal menggunakan Lean. Jika hasil ini akhirnya mampu melepasi tinjauan pakar, ia akan menggoyahkan hipotesis masa eksponen secara langsung.