ექსპონენციალური დროის ჰიპოთეზა (Exponential Time Hypothesis, ETH), კომპიუტერული მეცნიერების ერთ-ერთი ყველაზე ცნობილი დაშვება, კიდევ ერთხელ დადგა ეჭვქვეშ. OpenAI-ის შემდეგ Anthropic-მაც გამოაქვეყნა ნაშრომი, რომლის თანახმადაც კომპანიის შიდა კვლევითმა Claude მოდელმა 3-SAT ამოცანის ამოხსნის ახალი ალგორითმი იპოვა და ამით ETH უარყო. ნაშრომი 27 ოქტომბერს ატვირთეს Hexagon-ის პრეპრინტების არქივში, ხოლო Lean 4-ზე დაწერილი ფორმალური დამტკიცება კომპანიამ GitHub-ის ოფიციალურ რეპოზიტორიაში განათავსა.
Anthropic-ის ნაშრომში წერია, რომ ორი ლაბორატორიის მოდელებმა მსგავს შედეგს ერთმანეთისგან დამოუკიდებლად და ერთსა და იმავე დროს მიაღწიეს.
სარჩევი
რა არის ექსპონენციალური დროის ჰიპოთეზა
3-SAT ლოგიკური ამოცანაა: გვაქვს n რაოდენობის ცვლადი, რომელთაგან თითოეული შეიძლება იყოს „ჭეშმარიტი“ ან „მცდარი“, და პირობების ნაკრები. საჭიროა გავარკვიოთ, არსებობს თუ არა ცვლადების ისეთი კომბინაცია, რომელიც ყველა პირობას ერთდროულად აკმაყოფილებს. მზა პასუხის შემოწმება მარტივია, მაგრამ მისი პოვნა ძალიან რთულია: უხეში გადარჩევით 2n ვარიანტის შემოწმება მოგვიწევს. 1980-იანი წლებიდან მეცნიერები ამ მაჩვენებელს ნელ-ნელა აუმჯობესებდნენ და ბოლო რეკორდი დეტერმინისტული ალგორითმისთვის დაახლოებით 1.328n იყო.
ექსპონენციალური დროის ჰიპოთეზა, რომელიც 1999 წელს რასელ იმპალიაცომ და რამამოჰან პატურიმ ჩამოაყალიბეს, ამბობს, რომ 3-SAT-ის ამოხსნას ყოველთვის ექსპონენციალური დრო დასჭირდება, ანუ ცვლადების მატებასთან ერთად სამუშაო ძალიან სწრაფად გაიზრდება. ეს P და NP-ის ცნობილ პრობლემაზე უფრო ძლიერი დაშვებაა და მასზე ასობით სამეცნიერო ნაშრომია დაფუძნებული: გრაფების თეორიიდან გამოთვლით ბიოლოგიამდე და მონაცემთა ბაზებამდე.
რა იპოვა Claude-მა
ნაშრომის მიხედვით, Claude-ის ალგორითმი 3-SAT-ს 2o(n) დროში, ანუ „ქვეექსპონენციალურად“ ხსნის. უფრო მეტიც, ის უფრო რთულ ამოცანასაც, #3-SAT-ს წყვეტს: არა მხოლოდ ამბობს, არსებობს თუ არა ამონახსნი, არამედ ითვლის, რამდენი ასეთი კომბინაცია არსებობს. შედეგი k-SAT-ზეც ვრცელდება, სადაც თითო პირობაში k ცვლადი შეიძლება იყოს. ავტორები მეთოდის ძირითად ინსტრუმენტებად ტენზორულ ქსელებსა და რანგს ასახელებენ.
Anthropic-ის განცხადებით, ძირითადი ალგორითმი 16 ოქტომბერს იპოვა შიდა კვლევითმა Claude მოდელმა, ადამიანის ჩარევის გარეშე და დაახლოებით 14 მილიონი გამომავალი ტოკენის გამოყენებით. შემდეგ კომპანიის მკვლევრებმა Claude-თან ერთად ნაშრომის გადმოცემა დახვეწეს. ფორმალური დამტკიცებაც AI მოდელებმა დაწერეს Lean 4-ში, პროგრამაში, რომელიც მათემატიკური მსჯელობის ყოველ ნაბიჯს ავტომატურად ამოწმებს.
რას ნიშნავს ეს პრაქტიკაში
მნიშვნელოვანია, არ გადავაჭარბოთ: Anthropic-ის რეპოზიტორიის აღწერაში პირდაპირ წერია, რომ შედეგი მხოლოდ ასიმპტოტურია და ფორმულების პრაქტიკულ ამოხსნაზე არაფერს ამბობს. ნაშრომშივე აღნიშნულია, რომ ის P და NP-ის საკითხს პირდაპირ არ წყვეტს და NP-სრული ამოცანებისთვის პრაქტიკულ ალგორითმს არ იძლევა. ანუ ჩვეულებრივი SAT პროგრამები ხვალიდან უფრო სწრაფად არ იმუშავებს.
მეცნიერებისთვის კი შედეგი დიდი მნიშვნელობისაა. MIT-ის პროფესორმა რაიან უილიამსმა, რომელიც OpenAI-ის შედეგის შემოწმებას ხელმძღვანელობს, TechCrunch-თან საუბარში თქვა, რომ ექსპონენციალური დროის ჰიპოთეზაზე დაფუძნებული ბევრი ნაშრომი ხელახლა გადასახედი იქნება და ყველა კომპიუტერულმა მეცნიერმა P = NP-ის შესაძლებლობას ცოტა მეტი წონა უნდა მიანიჭოს. მისივე თქმით, მან OpenAI-ს ჰკითხა, ხომ არ საფრთხდება კრიპტოგრაფიული სისტემები, და კომპანიამ უპასუხა, რომ შეამოწმა და საკმაოდ დარწმუნებულია, რომ ასეთი საფრთხე არ არის.
რატომ არის ეს ასეთი მნიშვნელოვანი? ექსპონენციალური დროის ჰიპოთეზა მკვლევრებისთვის ერთგვარი „საყრდენი“ იყო: თუ ის ჭეშმარიტია, მაშინ ბევრი სხვა ამოცანაც აუცილებლად რთული უნდა იყოს. ამ მიდგომით ათეულობით შედეგი იყო მიღებული, რომლებიც ამბობდნენ, რომ ესა თუ ის ამოცანა უფრო სწრაფად ვერ ამოიხსნება. თუ ექსპონენციალური დროის ჰიპოთეზა მცდარია, ეს დასკვნები ავტომატურად ძალას კარგავს და თითოეული მათგანის ხელახალი შეფასება დასჭირდება.
ამბავს კონკურენციის ელფერიც აქვს. TechCrunch-ის ცნობით, Anthropic-ის მათემატიკოსმა ლევენტ ალპოგემ ივარაუდა, რომ OpenAI-ის შედეგები უკვე არსებულ სამუშაოებს ეფუძნებოდა, რამდენიმე საათში კი Anthropic-მა საკუთარი უარყოფა გამოაქვეყნა. ორივე შედეგი ჯერ კიდევ სამეცნიერო საზოგადოების დამოუკიდებელ შემოწმებას ელოდება.
AI მეცნიერებაში: ახალი ეტაპი
ბოლო კვირებში მსჯელობის მოდელები სულ უფრო ხშირად აქვეყნებენ შედეგებს ფუნდამენტურ მეცნიერებაში: ჯერ OpenAI-ის მათემატიკური აღმოჩენები, შემდეგ PSI-ის შედეგები კვანტურ ფიზიკაში, ახლა კი Anthropic-ის ნაშრომი. მათი საერთო ნიშანი Lean-ში ფორმალური დამტკიცებაა, რაც მეცნიერებს შემოწმებას უადვილებს. თუ გსურთ მეტი გაიგოთ თავად მოდელზე, იხილეთ ჩვენი სტატია Claude-ის შესაძლებლობების შესახებ.
შეჯამება
Anthropic-ის ნაშრომი აჩვენებს, რომ ექსპონენციალური დროის ჰიპოთეზის უარყოფა ერთი კომპანიის შემთხვევითი შედეგი აღარ არის: ორმა ლაბორატორიამ მსგავს დასკვნას დამოუკიდებლად მიაღწია და ორივემ Lean-ში შემოწმებადი დამტკიცება გამოაქვეყნა. ძლიერი მხარე სწორედ ეს ფორმალური შემოწმებაა, სუსტი კი ისაა, რომ შედეგს პრაქტიკული გამოყენება ჯერ არ აქვს და სრული დამოუკიდებელი რეცენზია ჯერ არ დასრულებულა. ქართველი სტუდენტებისა და მკვლევრებისთვის ეს კარგი მაგალითია, თუ როგორ იცვლება მეცნიერება: AI უკვე არა მხოლოდ კოდს წერს, არამედ ძველ ჰიპოთეზებსაც ამოწმებს.
წყაროები
სხვა თემები
AI აგენტის გავლენა: ანალიტიკოსები Claude Code-ის პოზიციას 86%-ში დაეთანხმნენ
Oracle და OpenAI: Oracle-ის აპლიკაციები ChatGPT-ში და 4 ახალი შეთავაზება
Anthropic წამლების შექმნაში: Claude ექვს პარტნიორთან და საკუთარ პროგრამებზე მუშაობს