GPT-5.6-ը մեկ հուշումով փակեց ուռուցիկ օպտիմիզացիայի 30-ամյա բացը

r/math ֆորումի գրառման համաձայն՝ GPT-5.6 Sol Pro-ն 1996 թվականից բաց մնացած ուռուցիկ օպտիմիզացիայի բարդության արդյունքի բացակայող կեսը ստացել է մեկ՝ 148 րոպե տևող սեսիայում։ Հարակից նախատպության հեղինակը նշում է, որ փաստարկը ֆորմալ կերպով ստուգվել է Lean-ում, և որ արդյունքը դեռ գրախոսություն չի անցել։

Իրականում ինչ էր բաց

Խոսքը դետերմինիստական զրոյական կարգի ուռուցիկ օպտիմիզացիայի մասին է։ Ալգորիթմը կարող է հարցում անել R^d-ի միավոր գնդի ցանկացած կետի և ստանում է միայն ուռուցիկ, 1-Լիպշիցյան ֆունկցիայի ճշգրիտ արժեքը՝ առանց գրադիենտի, իսկ մնացած առումով սահմանափակումներ չկան ոչ հաշվարկների, ոչ հիշողության վրա։ Նման խնդիրներ առաջանում են, երբ նպատակային ֆունկցիան գնահատվում է ֆիզիկական փորձով կամ սիմուլյատորով, և բնական հարցն այն է, թե սկզբունքորեն քանի գնահատում է անհրաժեշտ։ 1996 թվականին Պրոտասովը ներկայացրեց ալգորիթմ, որը ցույց է տալիս, որ d² կարգի գնահատումները բավարար են։ Սակայն դրան համապատասխանող ստորին գնահատականը բացակայում էր. այն ժամանակ կիրառելի ամենաուժեղ արդյունքը՝ Ω(d), ժառանգված էր առաջին կարգի ավելի ուժեղ մոդելից, որտեղ գրադիենտները հասանելի են, ինչը d-ում թողնում էր գծային բաց և վստահություն չէր տալիս, որ գրադիենտներն ընդհանրապես օգնում են։ Մոդելի ներկայացրած ապացույցը փակում է այդ բացը. ոչ մի ալգորիթմ չի կարող ավելի լավ լինել, քան d² կարգը, այսինքն՝ Պրոտասովի մեթոդը օպտիմալ է։

Տասը էջանոց հուշում, 148 րոպե

Հեղինակը, ով դասավանդում է Բերքլիի Կալիֆոռնիայի համալսարանում՝ արդյունաբերական ճարտարագիտության և գործառնական հետազոտությունների բնագավառում, խնդրի վրա աշխատել էր մոտ մեկ տարի՝ ընդհատումներով, և անհաջող փորձել էր GPT-5.4-ը և GPT-5.5-ը։ Այն բանից հետո, երբ OpenAI-ն հայտարարեց Cycle Double Cover-ի ապացույցի մասին, նա նույն ոճով գրեց մոտ տասը էջանոց հուշում՝ այն կցված է նախատպության վերջում, և պահանջեց քառակուսային ստորին գնահատականը d⁻⁴ կարգի ճշգրտությամբ։ 148 րոպե անընդհատ աշխատանքից հետո մոդելը վերադարձրեց ապացույց, որը չափողականությունից քառակուսային կախվածությունը հաստատում է d⁻³ կարգի ճշգրտությամբ։ Հեղինակն ինքը ստուգեց փաստարկը և ֆորմալ կերպով ապացուցեց այն Lean-ում։ Կառուցվածքը՝ աֆին ֆունկցիաների մաքսիմումը, կապված է Նեմիրովսկու և Յուդինի խիստ գնահատականի հիմքում ընկած կառուցվածքի հետ։

Ինչ է սա նշանակում հետազոտության համար

Նախատպությունը, Lean-ի պահոցը, ամբողջական հուշումը և սկզբնական զրույցների մատյանները հասանելի են գրառման հղումներով։ Հեղինակը զգույշ է պնդման մասշտաբի հարցում. ապացույցը ուռուցիկ երկրաչափության մեջ սկզբունքորեն նոր տեխնիկա չի ներմուծում, և, նրա փաստարկով, եթե արդյունքը հասանելի է գոյություն ունեցող մեթոդներով, ապա ժամանակակից արհեստական բանականության համակարգերը նույնպես կհասնեն դրան։ Նա չի կարծում, որ մաթեմատիկոսները կդառնան ավելորդ, սակայն ասում է, որ հեշտ և նույնիսկ չափավոր բարդ խնդիրների վրա աշխատելը կկորցնի իմաստը, և հետազոտողներին կմնան այն խնդիրները, որտեղ իսկապես նոր գաղափարներ են պետք։ Մեկնաբանները պատմում են նույն մոդելի նմանատիպ արդյունքների մասին, այդ թվում Սաբիդուսսիի համատեղելիության վարկածի ապացույցի և սխալները ուղղող կոդերում մեկ բաց խնդրի, որոնք երկուսն էլ հրապարակվել են arXiv-ում՝ Lean ֆորմալացումներով։ Ծախսերի մասին հարցին հեղինակը պատասխանում է, որ նախագիծը բաժանորդագրության 20-ից 200 դոլարի սահմանում է, իսկ մոդելի օգտագործման ընդհանուր ժամանակը չի գերազանցում մոտ տասնհինգ ժամը։