Në teorinë e kompleksitetit llogaritës, një reduktim në kohë polinomi është një metodë për zgjidhjen e një problemi duke përdorur një tjetër. Reduktimet në kohë polinomiale përdoren shpesh në teorinë e kompleksitetit për përcaktimin e klasave të kompleksitetit dhe problemeve të plota për ato klasa. …
Çfarë konsiderohet koha polinomiale?
Një algoritëm thuhet se është me kohë polinomi nëse koha e tij e funksionimit kufizohet sipër nga një shprehje polinomiale në madhësinë e hyrjes për algoritmin, që është, T(n)=O(nk) për disa konstante pozitive k.
Si e dini nëse diçka është një kohë polinomiale?
3 Përgjigje. Një algoritëm është polinom (ka kohë funksionimi polinom) nëse për disa k, C>0, koha e tij e ekzekutimit në hyrjet me madhësi n është maksimumi Cnk. Në mënyrë ekuivalente, një algoritëm është polinom nëse për disa k>0, koha e tij e funksionimit në hyrjet e madhësisë n është O(nk).
Çfarë ndodh nëse zvogëlimi lejohet në kohë eksponenciale?
Nëse reduktimi lejohet në kohë eksponenciale, atëherë mund të zgjidhë plotësisht problemin origjinal dhe të prodhojë një shembull të parëndësishëm të problemit të synuar Kjo do të thotë se çdo problem në NP është i reduktueshëm në çdo problem tjetër sipas këtij lloji reduktimesh, kështu që çdo problem në NP është NP-komplet për reduktimet eksponenciale të kohës.
Çfarë është një algoritëm eksponencial?
Një algoritëm thuhet se është kohë eksponenciale, nëse T(n) është sipër i kufizuar me 2poli( ) , ku poli(n) është një polinom në n. Më formalisht, një algoritëm është kohë eksponenciale nëse T(n) kufizohet me O(2nk) për një k. Ref:Wiki.
