Vai samazināšana ir polinoma laiks?

2024 Autors: Fiona Howard | [email protected]. Pēdējoreiz modificēts: 2024-01-10 06:40

Aprēķinu sarežģītības teorijā polinoma laika samazināšana ir metode vienas problēmas atrisināšanai, izmantojot citu. Polinoma laika samazinājumi bieži tiek izmantoti sarežģītības teorijā, lai definētu gan sarežģītības klases, gan šo klašu pilnīgas problēmas. …

Kas tiek uzskatīts par polinoma laiku?

Tiek uzskatīts, ka algoritmam ir polinoma laiks, ja tā darbības laiks ir augšējais, ko ierobežo polinoma izteiksme algoritma ievades lielumā, tas ir, T(n)=O(n^k) kādai pozitīvai konstantei k.

Kā zināt, vai kaut kas ir polinoma laiks?

3 atbildes. Algoritms ir polinoms (tam ir polinoma darbības laiks), ja kādam k, C>0, tā darbības laiks n izmēra ieejās ir ne vairāk kā Cnk. Līdzvērtīgi algoritms ir polinoms, ja kādam k>0 tā darbības laiks n izmēra ieejās ir O(nk).

Kas notiek, ja samazinājums ir atļauts eksponenciālā laikā?

Ja samazinājumam ir atļauts eksponenciāls laiks, tad tas var pilnībā atrisināt sākotnējo problēmu un radīt triviālu mērķa problēmas gadījumu Tas nozīmē, ka katra NP problēma ir reducējama uz katru cita problēma ar šāda veida samazinājumiem, tāpēc katra problēma NP ir NP pilnīga eksponenciālam laika samazinājumam.

Kas ir eksponenciālais algoritms?

Algoritms tiek uzskatīts par eksponenciālu laiku, ja T(n) augšējo robežu ierobežo 2^{poly( )} , kur poli(n) ir kāds n polinoms. Formālāk sakot, algoritms ir eksponenciāls laiks, ja T(n) ir ierobežots ar O(2^{nk) kādai konstantei k. Ref:Wiki.}