In de computationele complexiteitstheorie is een polynomiale tijdsreductie een methode om het ene probleem op te lossen met een ander. Polynomiale tijdreducties worden vaak gebruikt in de complexiteitstheorie voor het definiëren van zowel complexiteitsklassen als complete problemen voor die klassen. …
Wat wordt beschouwd als polynomiale tijd?
Er wordt gezegd dat een algoritme polynomiale tijd heeft als de looptijd wordt begrensd door een polynoomexpressie in de grootte van de invoer voor het algoritme, dat wil zeggen T(n)=O(nk) voor een positieve constante k.
Hoe weet je of iets een polynomiale tijd is?
3 Antwoorden. Een algoritme is polynoom (heeft een polynomiale looptijd) als voor sommige k, C>0, de looptijd ervan op ingangen met de grootte n ten hoogste Cnk is. Op equivalente wijze is een algoritme polynoom als voor sommige k>0 de looptijd op invoer met grootte n O(nk) is.
Wat gebeurt er als de reductie in exponentiële tijd wordt toegestaan?
Als de reductie exponentiële tijd wordt toegestaan, het kan het oorspronkelijke probleem volledig oplossen en een triviale instantie van het doelprobleem produceren Dit betekent dat elk probleem in NP herleidbaar is tot elke ander probleem door een dergelijk type reducties, dus elk probleem in NP is NP-compleet voor exponentiële tijdsreducties.
Wat is een exponentieel algoritme?
Een algoritme heet exponentiële tijd, if T(n) wordt als bovengrens begrensd door 2poly( ) , waarbij poly(n) een veelterm is in n. Meer formeel is een algoritme exponentiële tijd als T(n) wordt begrensd door O(2nk) voor een constante k. Ref:Wiki.
