OpenAI, Yeni Algoritmayla Üstel Zaman Hipotezini Çürüttüğünü İddia Ediyor

ChainCatcher haberine göre, OpenAI, bilgisayar biliminde yirmi yıldır kullanılan "Üstel Zaman Hipotezi"ni (ETH, Ethereum değil) çözdüğünü duyurdu. Bu hipotez, özellikle hesaplaması zor olan problemlerin ne kadar zor olduğunu inceler ve örnek olarak Boolean tatmin edilebilirlik problemi (SAT) verilir: Verilen bir mantıksal koşul kümesi için, tüm koşulları aynı anda sağlayan bir atama var mıdır? Problem boyutu büyüdükçe, bilinen en iyi yöntem temelde olası cevapları tek tek denemektir ve zaman maliyeti boyutla üstel olarak artar. Üstel Zaman Hipotezi, bu tür problemlerin temelde büyük ölçüde hızlandırılamayacağını ve gerçek anlamda alt-üstel zamanlı verimli algoritmaların olmadığını iddia eder. 1999 yılında ortaya atıldığından beri, bu hipotez teorik bilgisayar biliminin önemli bir temelini oluşturmuş ve birçok makale, bazı problemlerin zor olduğunu veya bazı algoritmaların neredeyse en iyilerini kanıtlamak için bu hipoteze dayanmıştır. Eğer Üstel Zaman Hipotezi çürütülürse, şu ana kadar neredeyse imkânsız olarak kabul edilen problemler için teorik olarak daha iyi çözümler olabilecektir. OpenAI, modelinin k-SAT probleminin çözümlerinin sayısını alt-üstel zamanda kesin olarak hesaplayan bir deterministik algoritma bulduğunu ve bunu Lean ile formel olarak doğruladığını iddia ediyor. Eğer bu sonuç uzmanların incelemesini başarıyla geçerse, Üstel Zaman Hipotezi doğrudan sarsılacaktır.