En la teoria de la complexitat computacional, una reducció de temps polinomial és un mètode per resoldre un problema utilitzant un altre. Les reduccions de temps polinomial s'utilitzen freqüentment en la teoria de la complexitat per definir tant classes de complexitat com problemes complets per a aquestes classes. …
Què es considera temps polinomial?
Es diu que un algorisme és de temps polinomi si el seu temps d'execució està limitat per una expressió polinomial de la mida de l'entrada per a l'algorisme, és a dir, T(n)=O(nk) per a alguna constant positiva k.
Com saps si alguna cosa és un temps polinomi?
3 respostes. Un algorisme és polinomi (té un temps d'execució polinomi) si per a alguns k, C>0, el seu temps d'execució en entrades de mida n és com a màxim Cnk. De manera equivalent, un algorisme és polinomi si per a alguns k>0, el seu temps d'execució en entrades de mida n és O(nk).
Què passa si la reducció es permet en temps exponencial?
Si es permet la reducció en temps exponencial, aleshores pot resoldre completament el problema original i produir una instància trivial del problema objectiu Això vol dir que tots els problemes de NP es poden reduir a tots els un altre problema per aquest tipus de reduccions, de manera que tots els problemes de NP són NP-complets per a reduccions de temps exponencials.
Què és un algorisme exponencial?
Es diu que un algorisme és temps exponencial, si T(n) està limitat per 2poly( ) , on poli(n) és algun polinomi en n. Més formalment, un algorisme és temps exponencial si T(n) està limitat per O(2nk) per a una k constant. Ref:Wiki.
