არის შემცირების დრო მრავალწევრი?

2024 ავტორი: Fiona Howard | [email protected]. ბოლოს შეცვლილი: 2024-01-10 06:39

გამოთვლითი სირთულის თეორიაში, პოლინომიური დროის შემცირება არის მეთოდი ერთი პრობლემის გადასაჭრელად მეორის გამოყენებით. პოლინომიური დროის შემცირება ხშირად გამოიყენება სირთულის თეორიაში, როგორც სირთულის კლასის, ასევე ამ კლასების სრული ამოცანების დასადგენად. …

რა ითვლება მრავალწევრი დრო?

ამბობენ, რომ ალგორითმი არის პოლინომიური დროის, თუ მისი მუშაობის დრო ზედა შემოსაზღვრულია პოლინომიური გამოსახულებით ალგორითმის შეყვანის ზომით, ანუ T(n)=O(n^k) ზოგიერთი დადებითი მუდმივი k.

როგორ იცით, არის თუ არა რამე მრავალწევრი დრო?

3 პასუხი. ალგორითმი არის პოლინომიური (აქვს პოლინომიური გაშვების დრო), თუ ზოგიერთი k, C>0, მისი მუშაობის დრო n ზომის შეყვანებზე არის მაქსიმუმ Cnk. ექვივალენტურად, ალგორითმი არის პოლინომიური, თუ ზოგიერთი k>0, მისი მუშაობის დრო n ზომის შეყვანებზე არის O(nk).

რა მოხდება, თუ შემცირება დაშვებულია ექსპონენციალურ დროში?

თუ შემცირების ნებადართულია ექსპონენციალური დრო, მაშინ მას შეუძლია სრულად გადაჭრას საწყისი პრობლემა და შექმნას სამიზნე ამოცანის ტრივიალური მაგალითი ეს ნიშნავს, რომ NP-ის ყველა პრობლემა შემცირდება ყველაზე. სხვა პრობლემა ასეთი ტიპის შემცირებით, ამიტომ NP-ში ყველა პრობლემა არის NP-სრული დროის ექსპონენციალური შემცირებისთვის.

რა არის ექსპონენციალური ალგორითმი?

ამბობენ, რომ ალგორითმი არის ექსპონენციალური დრო, თუ T(n) ზედა შემოსაზღვრულია 2^{პოლი( )} , სადაც პოლი(n) არის რამდენიმე მრავალწევრი n-ში. უფრო ფორმალურად, ალგორითმი არის ექსპონენციალური დრო, თუ T(n) შემოიფარგლება O(2^{nk) გარკვეული k მუდმივისთვის. Ref:Wiki.}