Компьютерийн шинжлэх ухааны 25 жилийн суурь онол нурав уу? OpenAI-ийн загвар "Exponential Time Hypothesis"-ийг няцаалаа

Компьютерийн шинжлэх ухааны суурь ойлголтууд нүдэн дээр маань шинэчлэгдэж байна уу? Сүүлийн хэдхэн цагийн дотор алгоритм, онолын тооцоолол болон хиймэл оюуны салбарыг донсолгосон том үйл явдал боллоо. OpenAI компани өөрийн дотоод хиймэл оюуны загвараар тооцооллын нарийн төвөгтэй байдлын (Computational Complexity Theory) хамгийн чухал тулгуур багануудын нэг болох "Exponential Time Hypothesis" (ETH)-ийг албан ёсоор няцаасан хэмээн зарлаж, судалгааны гар бичмэл болон Lean 4 математик баталгаажуулалтын кодыг GitHub дээр нээлттэй байршууллаа.

Хэрэв энэ баталгаа эрдэмтдийн нарийвчилсан шалгалтыг давж чадвал сүүлийн 25 жилийн турш алгоритмын хязгаарыг тодорхойлж ирсэн хэдэн зуун онол, таамаглал сууриараа өөрчлөгдөх юм.

"Exponential Time Hypothesis" (ETH) гэж чухам юу вэ?

Хөгжүүлэгч бүрийн мэдэх $P$ vs $NP$ асуудал нь "NP ангиллын бодлогуудыг полиномиаль ($O(n^k)$) хугацаанд бодох боломжтой юу?" гэж асуудаг. Ихэнх эрдэмтэд боломжгүй буюу $P \neq NP$ гэдэгт итгэдэг ч өнөөг хүртэл бүрэн баталж чадаагүй байгаа билээ.

Харин 1999 онд компьютер судлаач Рассел Импальяццо (Russell Impagliazzo) болон Рамамохан Патури (Ramamohan Paturi) нар үүнээс ч илүү прагматик бөгөөд хатуу таамаглал болох Exponential Time Hypothesis (ETH)-ийг дэвшүүлсэн юм.

Энгийнээр хэлбэл: 3-SAT (булийн илэрхийллийн хангагдах чанарын бодлого)-ийг ямар ч детерминистик алгоритм жинхэнэ экспоненциал хугацаанаас ($2^{\Omega(n)}$ буюу ямар нэг тогтмол $c > 0$-ийн хувьд $2^{cn}$ хугацаанаас) хурдан бодож чадахгүй гэж ETH үздэг.

Сүүлийн 25 жилийн хугацаанд график онол, сүлжээний оновчлол, биоинформатик, өгөгдлийн сангийн индексчлэл зэрэг олон салбарын хэдэн зуун эрдэм шинжилгээний ажил "Хэрэв ETH үнэн бол уг асуудлыг тэдэн секундээс хурдан бодох боломжгүй" гэсэн нөхцөлтэйгээр бүтээгдсэн байдаг.

AI яг яаж няцаав? Математик шийдэл

OpenAI-аас нийтэлсэн "The Exponential Time Hypothesis is False" гар бичмэлд дурдсанаар, загвар нь $k$-CNF томьёоны бүх хангагдах шийдлийг тоолдог (#k-SAT) цоо шинэ детерминистик алгоритмыг олж боловсруулжээ.

Уг алгоритмын хугацааны нарийн төвөгтэй байдал нь: $$2^{O\left(n \cdot \frac{(\log \log n)^2}{\sqrt{\log n}}\right)}$$ бөгөөд ердөө полиномиаль санах ой (polynomial space) ашигладаг болохыг Lean 4 интерактив теорем шалгагчаар кодчлон баталсан байна.

Математик үүднээс харвал зэрэгт дэх $\sqrt{\log n}$ хуваагч нь $n$ хязгааргүй рүү өсөх тусам утгыг нь бууруулж байдаг тул энэхүү ажиллах хугацаа нь ямар ч шугаман тогтмол $c \cdot n$-ээс асимптотоор хурдан (sub-exponential) болж хувирна. Өөрөөр хэлбэл, 3-SAT бодлогод $2^{cn}$ гэсэн үл давах доод хязгаар оршдоггүй болохыг харуулж, ETH-ийг шууд утгаар нь няцааж байгаа юм.

Практикт энэ нь юу гэсэн үг вэ? Манай криптограф сүйрэх үү?

Олон хөгжүүлэгчид "Хэрэв 3-SAT дэд экспоненциал хугацаанд бодогддог болсон юм бол RSA, ECC нууцлал, крипто системүүд маань шууд эвдэрнэ гэсэн үг үү?" гэж асууж байж болох юм.

Хариулт нь: Үгүй, айх аюулгүй.

Үүнд хоёр том шалтгаан бий:

Тэнгэрийн алгоритм (Galactic Algorithm): AI-ийн олсон энэхүү дэвшил нь асимптот (маш асар том $n$-ийн хувьд) чанартай. Формула дахь $\sqrt{\log n}$ хуваагч нь бодит амьдрал дээр маш удаан өсдөг. Практикт компьютерт ажиллах бодит хэмжээний өгөгдөл дээр энэ нь ердийн бүдүүлэг хүчний (brute-force) экспоненциал хайлтаас бараг ялгаагүй удаан хэвээр байх болно.
Криптосистемийн үндэс өөр: Орчин үеийн криптограф (жишээ нь RSA, Elliptic Curve, эсвэл квантын дараах Lattice криптограф) нь 3-SAT-ийн хүндрэл дээр биш, факторизаци, салангид логарифм болон торон бүтцийн өвөрмөц бодлогууд дээр суурилдаг. MIT-ийн нэрт онолч Райан Уильямс (Ryan Williams) OpenAI-д хандаж хамгийн түрүүнд одоогийн ашиглагдаж буй крипто системүүд аюулгүй эсэхийг шалгуулахад тэдгээрт шууд аюул занал учрахгүй нь тогтоогдсон байна.

Гэсэн хэдий ч онолын компьютерийн шинжлэх ухаанд энэ нь жинхэнэ газар хөдлөлт юм. Өнөөг хүртэл "ETH үнэн" гэсэн суурь таамаг дээр босгосон хэдэн мянган онолын судалгаануудыг дахин эргэж харах шаардлага тулгарч байна.

Шинжлэх ухааны нээлт хийх шинэ соёл: Lean ба Shepherds

Энэхүү зарлалын хамгийн сонирхолтой хэсэг нь OpenAI-ийн уг нээлтийг олон нийтэд танилцуулсан хэлбэр байв. AI лабууд урьд өмнө нь "Манай модел нээлт хийлээ" гэж хоосон PR цацдаг байсан бол энэ удаад дараах өвөрмөц зарчмаар ажиллажээ:

Машинаар шалгагдсан нотолгоо: Байгалийн хэлээр бичсэн математик өгүүллээс гадна Lean теорем нотлогч хэл дээрх кодыг нь шууд нээлттэй GitHub репо дээр тавьсан.
Эздийг нь урьсан хамтын ажиллагаа: OpenAI өөрсдөө "Бид нээлт хийлээ" гэж ганцаар зүтгэхийн оронд яг уг ETH таамгийг 25 жилийн өмнө дэвшүүлсэн Рассел Импальяццо, Рамамохан Патури болон алгоритмын суурь судалгааны манлайлагч Райан Уильямс нарт хандан, хөндлөнгийн баталгаажуулалтын ажлын хэсгийг (external collaborators) ахлуулахаар тохиролцсон байна.

Үүнтэй зэрэгцэн OpenAI анализын салбарын алдарт Kakeya таамаглал (Sogge-ийн долгионы тэгшитгэлийн локал гөлгөржилт) болон квант талбарын онолын (Yang-Mills) цоо шинэ математик шийдлүүдийг зарласан нь AI салбар зөвхөн код бичих биш, хүний ойлголтын хязгаарыг давахад бэлэн болсны дохио юм.

Дүгнэлт: Хөгжүүлэгчдэд яагаад хамаатай вэ?

Олон жилийн турш хиймэл оюун ухааны загваруудыг бид зөвхөн "интернэт дэх текстийг нэгтгэн найруулагч статистик тоть" гэж харж ирсэн. Гэвч хүний 25 жил гацаж, эргэлзэж ирсэн суурь математик саадуудыг Lean хэлээр системтэйгээр задлан шийдэж эхэлсэн нь бид шинэ үе шатанд ирснийг харуулж байна.

Хэрэв та алгоритм, тооцооллын нарийн төвөгтэй байдал, формал баталгаажуулалтыг сонирхдог бол GitHub дээрх openai/math репозиторыг үзэж, Lean кодыг нь биечлэн туршиж үзэхийг зөвлөж байна!

Эх сурвалж: OpenAI Research (Working with academic communities to build scientific understanding), GitHub (openai/math - The Exponential Time Hypothesis is False), Hacker News, Techmeme.