Polinomska prevedljivost

Iz MaFiRaWiki

Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?

Pravimo, da je problem P polinomsko prevedljiv na problem P', če obstaja tak algoritem f: P → P' s polinomsko časovno zahtevnostjo, da je za vsako nalogo N problema P odgovor na to nalogo pritrdilen natanko tedaj, ko je odgovor na nalogo N'=f(N) problema P' pritrdilen.

V praksi to pomeni, da nalogo N v sklopu problema P v polinomskem času prevedemo na nalogo N', ki jo znamo rešiti v sklopu problema P'.


Glej tudi

Osebna orodja