კლასი NP, რომელიც ნიშნავს არადეტერმინისტულ პოლინომიურ დროს, არის ცენტრალური გამოთვლითი სირთულის თეორიაში და მოიცავს გადაწყვეტილების ამოცანებს, რომლებსაც აქვთ პოლინომიური დროის გადამოწმებები. გადაწყვეტილების პრობლემა არის ის, რომელიც მოითხოვს დიახ-ან-არა პასუხს, და ამ კონტექსტში შემმოწმებელი არის ალგორითმი, რომელიც ამოწმებს მოცემული ამოხსნის სისწორეს.
მნიშვნელოვანია განვასხვავოთ პრობლემის გადაჭრა (გამოთვლა) და გადაწყვეტის გადამოწმება (დამოწმება). NP-ში ყურადღება გამახვილებულია იმაზე, არის თუ არა პოლინომიური დროის დამადასტურებელი, რომელსაც შეუძლია დაადასტუროს ამოხსნის სისწორე.
კლასი P, რომელიც წარმოადგენს პოლინომიურ დროს, მოიცავს გადაწყვეტილების ამოცანებს, რომლებიც ამოხსნადია დეტერმინისტული ტურინგის მანქანით პოლინომიურ დროში. ამრიგად, P-ში ყველა პრობლემისთვის არის არა მხოლოდ პოლინომიური დროის ალგორითმი ამონახსნის მოსაძებნად, არამედ ასევე არის პოლინომიური დროის ალგორითმი ამოხსნის დასადასტურებლად.
ერთი შეხედვით წინააღმდეგობა მდგომარეობს იმაში, რომ P-ში ყველა პრობლემას, რომელსაც თან ახლავს პოლინომიური დროის ამოხსნის ალგორითმი, ასევე გააჩნია პოლინომიური დროის დამადასტურებელი. თუმცა, ეს არ ეწინააღმდეგება NP-ის განმარტებას. NP-ის განმსაზღვრელი მახასიათებელია პოლინომიური დროის გადამოწმების არსებობა, მიუხედავად იმისა, რამდენი ხანი შეიძლება დასჭირდეს ამოხსნის პოვნას. ეს ნიშნავს, რომ P-ში ყველა პრობლემა ასევე არის NP-ში, რადგან მათი ამონახსნები შეიძლება დამოწმებული იყოს პოლინომიურ დროში.
მაგალითად, განიხილეთ მარტივი რიცხვების ტესტირების პრობლემა. ეს პრობლემა შეიძლება ჩამოყალიბდეს ორი გზით: მარტივი რიცხვების გენერირება და იმის დადასტურება, არის თუ არა მოცემული რიცხვი მარტივი. ერატოსთენეს საცერი არის ალგორითმი ყველა მარტივი რიცხვის გენერირებისთვის გარკვეულ ზღვარამდე და ამას ეფექტურად აკეთებს, მაგრამ მისი დროის სირთულე არ არის პოლინომიური მკაცრი გაგებით, რომელიც გამოიყენება გამოთვლითი სირთულის თეორიაში; მას ხშირად აღნიშნავენ, როგორც O(n log log n), რაც უკეთესია, ვიდრე წრფივი, მაგრამ არა მკაცრად პოლინომიური P-ს განმარტებით. მეორეს მხრივ, მოცემული რიცხვის მარტივია თუ არა შემოწმების პრობლემა (პირველი რიცხვის ტესტირება) არის. განსხვავებული დავალება. ეფექტური ალგორითმები, როგორიცაა AKS primality ტესტი, საშუალებას იძლევა პირველადი გადამოწმება პოლინომიურ დროში. მაშასადამე, მარტივი რიცხვების ტესტირების პრობლემა, გადამოწმების კონტექსტში, მიეკუთვნება P კლასს, ისევე როგორც NP, რადგან ამონახსნის (არის თუ არა რიცხვი მარტივი) შემოწმება შესაძლებელია პოლინომიურ დროში. ეს გვიჩვენებს, რომ მიუხედავად იმისა, რომ მარტივი რიცხვების გენერაცია და მარტივი რიცხვების ტესტირება დაკავშირებულია, ისინი მოიცავს სხვადასხვა მოსაზრებებს გამოთვლითი სირთულის თვალსაზრისით.
დასკვნის სახით, NP-ის განმარტება, როგორც პოლინომიური დროის გადამოწმების მქონე, ემთხვევა P-ს ბუნებას. განსხვავება არ არის გადამოწმების საფეხურზე, არამედ ამონახსნების ძიების პროცესში: P ამოცანები ამოსახსნელია და დამოწმებულია პოლინომიურ დროში, ხოლო NP ამოცანები. გადამოწმებადია მრავალწევრულ დროში, მაგრამ ყოველთვის არ არის ცნობილი, შესაძლებელია თუ არა მათი ამოხსნა მრავალწევრულ დროში.
სხვა ბოლოდროინდელი კითხვები და პასუხები სირთულე:
- PSPACE კლასი არ არის EXPSPACE კლასის ტოლი?
- არის P სირთულის კლასი PSPACE კლასის ქვესიმრავლე?
- შეგვიძლია დავამტკიცოთ, რომ Np და P კლასი ერთნაირია, თუ ვიპოვით ეფექტური პოლინომიური ამოხსნის ნებისმიერი NP სრული ამოცანის დეტერმინისტულ TM-ზე?
- შეიძლება NP კლასი იყოს EXPTIME კლასის ტოლი?
- არის თუ არა პრობლემები PSPACE-ში, რომლისთვისაც არ არის ცნობილი NP ალგორითმი?
- შეიძლება თუ არა SAT პრობლემა იყოს NP სრული პრობლემა?
- შეიძლება თუ არა პრობლემა იყოს NP სირთულის კლასში, თუ არსებობს არადეტერმინისტული ტურინგ მანქანა, რომელიც გადაჭრის მას პოლინომიურ დროში
- NP არის ენების კლასი, რომლებსაც აქვთ დროის პოლინომიური გადამოწმებები
- არის P და NP რეალურად ერთი და იგივე სირთულის კლასი?
- არის ყველა კონტექსტის თავისუფალი ენა P სირთულის კლასში?
იხილეთ მეტი კითხვა და პასუხი სირთულის განყოფილებაში