NP არის ენების კლასი, რომლებსაც აქვთ დროის პოლინომიური გადამოწმებები
კლასი NP, რომელიც ნიშნავს "არადეტერმინისტული პოლინომიური დრო", არის ფუნდამენტური კონცეფცია გამოთვლითი სირთულის თეორიაში, თეორიული კომპიუტერული მეცნიერების ქვედარგში. NP-ის გასაგებად, პირველ რიგში, უნდა გაითავისოთ გადაწყვეტილების პრობლემების ცნება, რომელიც არის კითხვები დიახ ან არა პასუხით. ენა ამ კონტექსტში ეხება სტრიქონების ერთობლიობას რომელიმე ანბანზე, სადაც თითოეული სტრიქონი შიფრავს გადაწყვეტილების პრობლემის მაგალითს.
ენა (L) არის NP-ში, თუ არსებობს პოლინომიური დროის დამადასტურებელი (L). ვერიფიკატორი არის დეტერმინისტული ალგორითმი (V), რომელიც იღებს ორ შეყვანას: მაგალითად (x) და სერთიფიკატს (y). მოწმობა (y) ასევე ცნობილია როგორც "მოწმე" ან "მტკიცებულება". დამადასტურებელი (V) ამოწმებს თუ არა სერტიფიკატი (y) ადასტურებს, რომ (x) ეკუთვნის ენას (L). ფორმალურად, ენა (L) არის NP-ში, თუ არსებობს პოლინომი-დროის ალგორითმი (V) და პოლინომი (p(n)) ისეთი, რომ ყველა სტრიქონისთვის (x L-ში), არსებობდეს სტრიქონი (y) |y|. leq p(|x|)) და (V(x, y) = 1). პირიქით, ყველა სტრიქონისთვის (x notin L), არ არის ისეთი სტრიქონი (y), რომ (V(x, y) = 1).
ამ კონცეფციის გასარკვევად, განვიხილოთ ცნობილი პრობლემა „ბულის დაკმაყოფილების“ (SAT). SAT პრობლემა სვამს კითხვას, არის თუ არა ცვლადებისთვის ჭეშმარიტების მნიშვნელობების მინიჭება მოცემულ ლოგიკურ ფორმულაში, რომ ფორმულა შეფასდეს ჭეშმარიტად. SAT პრობლემა არის NP-ში, რადგან ლოგიკური ფორმულის (phi) და მის ცვლადებზე ჭეშმარიტების მნიშვნელობების (ალფა) მინიჭების გათვალისწინებით, შეიძლება პოლინომიურ დროში გადაამოწმოთ (alpha) აკმაყოფილებს (phi). აქ, მაგალითი ( x) არის ლოგიკური ფორმულა (phi), ხოლო სერთიფიკატი (y) არის დავალება (ალფა). ვერიფიკატორი (V) ამოწმებს (ალფა) აქცევს თუ არა (phi) ჭეშმარიტს, რაც შეიძლება გაკეთდეს პოლინომიურ დროში (phi) ზომის მიმართ.
კიდევ ერთი საილუსტრაციო მაგალითია „ჰამილტონის ბილიკის“ პრობლემა. ეს პრობლემა სვამს კითხვას, არის თუ არა მოცემულ გრაფიკში ბილიკი, რომელიც თითოეულ წვეროს ზუსტად ერთხელ ეწვევა. ჰამილტონის ბილიკის პრობლემა ასევე არის NP-ში, რადგან გრაფიკის (G) და წვეროების მიმდევრობის (P) გათვალისწინებით, შეიძლება პოლინომიურ დროში გადაამოწმოთ არის თუ არა (P) ჰამილტონის გზა (G). ამ შემთხვევაში ინსტანცია ( x ) არის გრაფიკი ( G ), ხოლო სერტიფიკატი ( y ) არის წვეროების თანმიმდევრობა ( P ). ვერიფიკატორი ( V ) ამოწმებს, ქმნის თუ არა ( P ) ჰამილტონის ბილიკს, რომელიც შეიძლება გაკეთდეს პოლინომიურ დროში (G ) ზომის მიმართ.
პოლინომიური დროის გადამოწმებადობის კონცეფცია მნიშვნელოვანია, რადგან ის იძლევა საშუალებას დახასიათდეს პრობლემები, რომლებიც ეფექტურად შესამოწმებელია, მაშინაც კი, თუ ამოხსნის პოვნა შესაძლოა გამოთვლით შეუძლებელია. ეს მივყავართ ცნობილ კითხვამდე, თუ არა (P = NP), რომელიც სვამს კითხვას, შესაძლებელია თუ არა ყველა პრობლემა, რომლის ამოხსნის შემოწმება შესაძლებელია მრავალწევრულ დროში, ასევე გადაიჭრება მრავალწევრულ დროში. კლასი (P) შედგება გადაწყვეტილების ამოცანებისგან, რომლებიც შეიძლება ამოხსნას მრავალწევრულ დროში დეტერმინისტული ტურინგის მანქანით. თუ (P = NP), ეს ნიშნავს, რომ პოლინომიური დროის გადამოწმების ყველა პრობლემას ასევე აქვს პოლინომიური დროის ამომხსნელი. ეს კითხვა რჩება ერთ-ერთ ყველაზე მნიშვნელოვან ღია პრობლემად კომპიუტერულ მეცნიერებაში.
NP-ის ერთ-ერთი მთავარი თვისება ის არის, რომ ის დახურულია პოლინომიური დროის შემცირების პირობებში. პოლინომიური დროის შემცირება ენიდან ( L_1 ) ენაზე ( L_2 ) არის მრავალწევრიანი დროის გამოთვლითი ფუნქცია ( f ) ისეთი, რომ ( x L_1 ში ) თუ და მხოლოდ თუ ( f(x) L_2 ში). თუ არსებობს პოლინომიური დროის შემცირება (L_1)-დან (L_2)-მდე და (L_2) არის NP-ში, მაშინ (L_1) ასევე არის NP-ში. ეს თვისება არის ინსტრუმენტული NP-სისრულის შესწავლაში, რომელიც განსაზღვრავს NP-ში „ურთულეს“ პრობლემებს. პრობლემა არის NP-სრული, თუ ის არის NP-ში და NP-ის ყველა პრობლემა შეიძლება შემცირდეს მასზე პოლინომიურ დროში. SAT პრობლემა იყო პირველი პრობლემა, რომელიც დადასტურდა, რომ არის NP-სრული და ის ემსახურება სხვა პრობლემების NP-სისრულის დასამტკიცებლად.
პოლინომიურ-დროის გადამოწმებადობის კონცეფციის შემდგომი საილუსტრაციოდ, განიხილეთ პრობლემა „ქვესიმრავლეების ჯამი“. ეს პრობლემა სვამს კითხვას, არის თუ არა მთელი რიცხვების მოცემული სიმრავლის ქვესიმრავლე, რომელიც ჯდება განსაზღვრულ სამიზნე მნიშვნელობასთან. ქვესიმრავლე ჯამის პრობლემა არის NP-ში, რადგან მთელი რიცხვების სიმრავლის ( S ), სამიზნე მნიშვნელობის (t) და ქვესიმრავლის (S') (S) სიმრავლის გათვალისწინებით, შეიძლება პოლინომიურ დროში გადაამოწმოთ თუ არა ელემენტების ჯამი (S') უდრის (t). აქ ინსტანცია ( x) არის წყვილი ( (S, t)), ხოლო სერტიფიკატი (y) არის ქვესიმრავლე (S'). შემმოწმებელი (V) ამოწმებს არის თუ არა (S') ელემენტების ჯამი (t), რაც შეიძლება გაკეთდეს პოლინომიურ დროში (S) ზომასთან მიმართებაში.
პოლინომიური დროის გადამოწმების მნიშვნელობა სცილდება თეორიულ მოსაზრებებს. პრაქტიკული თვალსაზრისით, ეს ნიშნავს, რომ NP-ში არსებული პრობლემების შემთხვევაში, შემოთავაზებული გადაწყვეტის (სერთიფიკატის) მოწოდების შემთხვევაში, შესაძლებელია მისი ეფექტურად შემოწმება. ეს მნიშვნელოვან გავლენას ახდენს კრიპტოგრაფიულ პროტოკოლებზე, ოპტიმიზაციის პრობლემებზე და სხვადასხვა სფეროებზე, სადაც მნიშვნელოვანია გადაწყვეტის სისწორის შემოწმება.
რომ შევაჯამოთ, NP კლასი მოიცავს გადაწყვეტილების ამოცანებს, რომლებისთვისაც შემოთავაზებული ამონახსნი შეიძლება გადამოწმდეს პოლინომიურ დროში დეტერმინისტული ალგორითმით. ეს კონცეფცია ფუნდამენტურია გამოთვლითი სირთულის თეორიაში და აქვს ღრმა გავლენა კომპიუტერული მეცნიერების როგორც თეორიულ, ასევე პრაქტიკულ ასპექტებზე. NP-ის შესწავლა, პოლინომიური დროის გადამოწმება და მასთან დაკავშირებული ცნებები, როგორიცაა NP-სისრულეობა, კვლავ რჩება კვლევის აქტიურ და კრიტიკულ სფეროდ.
სხვა ბოლოდროინდელი კითხვები და პასუხები სირთულე:
- PSPACE კლასი არ არის EXPSPACE კლასის ტოლი?
- არის P სირთულის კლასი PSPACE კლასის ქვესიმრავლე?
- შეგვიძლია დავამტკიცოთ, რომ Np და P კლასი ერთნაირია, თუ ვიპოვით ეფექტური პოლინომიური ამოხსნის ნებისმიერი NP სრული ამოცანის დეტერმინისტულ TM-ზე?
- შეიძლება NP კლასი იყოს EXPTIME კლასის ტოლი?
- არის თუ არა პრობლემები PSPACE-ში, რომლისთვისაც არ არის ცნობილი NP ალგორითმი?
- შეიძლება თუ არა SAT პრობლემა იყოს NP სრული პრობლემა?
- შეიძლება თუ არა პრობლემა იყოს NP სირთულის კლასში, თუ არსებობს არადეტერმინისტული ტურინგ მანქანა, რომელიც გადაჭრის მას პოლინომიურ დროში
- არის P და NP რეალურად ერთი და იგივე სირთულის კლასი?
- არის ყველა კონტექსტის თავისუფალი ენა P სირთულის კლასში?
- არის თუ არა წინააღმდეგობა NP-ის, როგორც გადაწყვეტილების ამოცანების კლასის განმარტებას პოლინომიურ-დროის შემმოწმებელებთან და იმ ფაქტს შორის, რომ P კლასში არსებულ ამოცანებს ასევე აქვთ პოლინომიური დროის გადამოწმებები?
იხილეთ მეტი კითხვა და პასუხი სირთულის განყოფილებაში