Je redukce polynomiální čas?

2025 Autor: Fiona Howard | [email protected]. Naposledy změněno: 2025-01-22 18:35

V teorii výpočetní složitosti je redukce polynomiálního času metodou pro řešení jednoho problému pomocí jiného. Polynomiální redukce času se často používají v teorii složitosti pro definování jak tříd složitosti, tak úplných problémů pro tyto třídy. …

Co se považuje za polynomiální čas?

O algoritmu se říká, že má polynomiální čas, pokud je jeho doba běhu horní ohraničena polynomickým výrazem ve velikosti vstupu pro algoritmus, tj. T(n)=O(n^k) pro nějakou kladnou konstantu k.

Jak poznáte, že je něco polynomiální čas?

3 odpovědi. Algoritmus je polynomiální (má polynomiální dobu běhu), pokud pro nějaké k, C>0 je jeho doba běhu na vstupech o velikosti n nejvýše Cnk. Ekvivalentně je algoritmus polynomiální, pokud pro některé k>0 je jeho doba běhu na vstupech o velikosti n O(nk).

Co se stane, když je povoleno snížení v exponenciálním čase?

Pokud je redukce povolena exponenciálně, pak může plně vyřešit původní problém a vytvořit triviální instanci cílového problému To znamená, že každý problém v NP je redukovatelný na každý jiný problém u takového typu redukce, takže každý problém v NP je NP-úplný pro exponenciální redukce času.

Co je to exponenciální algoritmus?

Algoritmus se nazývá exponenciální čas, pokud T(n) je horní ohraničeno 2^{poly( )} , kde poly(n) je nějaký polynom v n. Více formálně, algoritmus je exponenciální čas, jestliže T(n) je ohraničený O(2^{nk) pro nějakou konstantu k. Ref:Wiki.}