A redukciós idő polinomiális?

2024 Szerző: Fiona Howard | [email protected]. Utoljára módosítva: 2024-01-10 06:38

A számítási komplexitás elméletében a polinomiális idejű redukció egy probléma megoldásának módszere egy másik felhasználásával. A polinomidő-redukciókat gyakran használják a komplexitáselméletben mind a komplexitási osztályok, mind az osztályok teljes problémáinak meghatározására. …

Mit tekintünk polinomiális időnek?

Egy algoritmusról azt mondjuk, hogy polinomiális idejű, ha futási idejét felső határa egy polinomiális kifejezés az algoritmus bemenetének méretében, azaz T(n)=O(n^k) valamilyen pozitív k állandóra.

Honnan tudod, hogy valami polinomiális idő?

3 Válaszok. Egy algoritmus akkor polinomiális (polinomiális futási ideje van), ha valamilyen k esetén (C>0) a futási ideje n méretű bemeneteken legfeljebb Cnk. Ennek megfelelően egy algoritmus polinom, ha valamilyen k>0 esetén a futási ideje n méretű bemeneteken O(nk).

Mi történik, ha a csökkentést exponenciális időben engedélyezzük?

Ha a redukciót exponenciális időre engedélyezzük, akkor teljesen megoldhatja az eredeti problémát, és előállíthatja a célprobléma triviális példányát Ez azt jelenti, hogy az NP-ben minden probléma visszavezethető mindenre egy másik probléma az ilyen típusú redukciókkal, tehát az NP-ben minden probléma NP-teljes az exponenciális időcsökkentéshez.

Mi az exponenciális algoritmus?

Egy algoritmusról azt mondják, hogy exponenciális idő, ha T(n) felső határa 2^{poly( )} , ahol a poli(n) valamilyen polinom az n-ben. Formálisabban egy algoritmus exponenciális idő, ha T(n)-t O(2^{nk) határolja valamilyen k állandó esetén. Ref:Wiki.}