მკვლევარებმა წმ. ენდრიუს უნივერსიტეტიდან განაცხადეს, რომ ნებისმიერი პროგრამისტი, რომეილც თავს გაართმევს  ცნობილი “დედოფლის თავსატეხი”-ის კომოიუტერისათვის მარტივად გადაწყვეტის ალგორითმის პოვნას, შეძლებს მთელი IT ინდუსტრიის შეცვლას და ამასთან ერთად მიიღებს ამერიკის მათემატიკის ინსტიტუტის  დაწესებულ ფულად პრიზს 1 მილიონი დოლარის ოდენობით.

დედოფლის თავსატეხი გულისხმობს შემდეგს:  ჭადრაკის დაფაზე განათვსე რვა დედოფალი ისე, რომ  არცერთ ორ დედოფალს არ შეეძლოს ერთმანეთის შეტევა, შესაბამისად არცერთი დედოფალი არ უნდა მოხვდეს ერთ სვეტზე, რიგსა თუ დიაგონალზე. თავსატეხი პირველად 1850 წელს შემოგვთავაზეს და შეიძლება ითქვას მისი გადაწყვეტა ნებისმიერ ადამიანს შეუძლია . (იხ სურათი სტატიის ბოლოს)

თუმცა კომპიუტერის შემთხვევაში საქმე რთულადაა, მას ამ ამოცანის მარტივად გადაწყვეტა არ შეუძლია. კომპიუტერი დღევანდელი ალგორითმის გათვალისწინებით, პრობლემის გადაჭრისას, გადის მისი გადაჭრის ყველა შესაძლო ვარიანტს, შესაბამისად რაც უფრო მეტი ვარიანტია მით მეტი დრო სჭირდება კომპიუტერს პასუხის მისაგნებად. Journal of Artificial Intelligence-ის სტატიის მიხედვით, მას შემდეგ რაც ჭადრაკის დაფა კომპიუტერული კალკულაციისას ხდება 1,000 უჯრა 1,000 უჯრაზე მას უკვე ამ ამოცანასთან გამკლავება უბრალოდ აღარ შეუძლია.

“თუ თქვენ შეძლებთ კომპიუტერული პროგრამის დაწერას, რომელიც ამ თავსატეხს ძალიან მალე გადაჭრის, შემდგომ ამ მეთოდის ადაპტირება სხვა ძალიან მნიშვნელოვანი პრობლემების გადასაწყვეტად იქნება შესაძლებელი, რომელიც თითოეულ ჩვენთაგანს ყოველდღიურად გვეხება” ამბობს ავტორი იან გენტი განცხადებაში.

“პროგრამის მეშვეობით, შესაძლებელი იქნება ისეთი ტრივიალური გამოწვევების გადაწყვეტა, მაგალითად როგორიცაა, თქვენი ფეისბუქ მეგობრების ყველაზე დიდი ჯგუფის გამოვლენა რომელიც ერთმანეთს არ იცნობს ან ისეთი ძალიან მნიშვნელოვანი გამოწვევა, როგორიცაა იმ კოდის გატეხვა, რომლის მეშვეობითაც, ჩვენს ონლაინ ტრანზაქციების  უსაფრთხოებას ვინარჩუნებთ”.

ეს კონკრეტული მაგალითი ცნობილი კომპიუტერული პრობლემის, “P versus NP” -ის ვარიაციაა. ამ პრობლემის არსი შემდეგია: შესაძლებელია, თუ არა ნებისმიერი იმ პრობლემის სწრაფი გადაწყვეტა, რომლის იდენტიფიცირებაც მციერ დროში ხდება? მაგალითად, თუ თქვენ გეტყვიან, რომ იპოვოთ ციფრი 4,199 გამყოფები ამისათვის საკმაო დრო დაგჭირდებათ. თუმცა იმის დადგენა, რომ 4199 იყოფა მხოლოდ 13, 17 და 19-ზე საკმაოდ მარტივია (ასევე 1 და თავისი თავი).

დიდ ნაწილს, სჯერა რომ ყველა იმ პრობლემის გადაწყვეტა სწრაფად არ არის შესაძლებელი, რომელიც იდენტიფიცირდება მოკლე დროში, თუმცა თუ ფიქრობთ, რომ შეძლებთ ალგორითმის დაწერას, რომელიც ამ ამოცანის შესრულებას შეძლებს (ან დაამტკიცებთ, რომ ეს შესაძლებელია), მკვლევარები სიამოვნებით მოგისმენენ.

“დაწესებულია პრიზი, 1,000,000 დოლარის ოდენობით იმისთვის, ვინც დაამტკიცებს, რომ “დედოფლის ტავსატეხი”-ის გადაწყვეტა შესაძლებელია მარტივად” ამბობს კვლევის თანაავტორი კრისტოფერ ჯეფერსონი.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

“დედოფლის თავსატეხი”-ის ერთერთი გადაჭრის მეთოდი.

წყარო: iflscience