Polynomial time ba ang reduction?

2024 May -akda: Fiona Howard | [email protected]. Huling binago: 2024-01-10 06:44

Sa computational complexity theory, ang polynomial-time reduction ay isang paraan para sa paglutas ng isang problema gamit ang isa pang. Ang mga polynomial-time reductions ay madalas na ginagamit sa complexity theory para sa pagtukoy sa parehong kumplikadong klase at kumpletong mga problema para sa mga klase. …

Ano ang itinuturing na polynomial time?

Ang isang algorithm ay sinasabing polynomial time kung ang oras ng pagpapatakbo nito ay nasa itaas na hangganan ng polynomial expression sa laki ng input para sa algorithm, ibig sabihin, T(n)=O(n^k) para sa ilang positibong constant k.

Paano mo malalaman kung ang isang bagay ay polynomial time?

3 Sagot. Ang isang algorithm ay polynomial (may polynomial running time) kung para sa ilang k, C>0, ang oras ng pagpapatakbo nito sa mga input ng laki n ay hindi hihigit sa Cnk. Katulad nito, ang isang algorithm ay polynomial kung para sa ilang k>0, ang oras ng pagtakbo nito sa mga input ng laki n ay O(nk).

Ano ang mangyayari kung pinapayagan ang pagbawas sa exponential time?

Kung ang pagbabawas ay pinahihintulutan ng exponential time, pagkatapos ay ito ay ganap na malulutas ang orihinal na problema at makagawa ng isang maliit na halimbawa ng target na problema Ito ay nangangahulugan na ang bawat problema sa NP ay mababawasan sa bawat ibang problema sa pamamagitan ng ganitong uri ng pagbabawas, kaya ang bawat problema sa NP ay NP-kumpleto para sa exponential time reductions.

Ano ang exponential algorithm?

Ang isang algorithm ay sinasabing exponential time, kung ang T(n) ay upper bounded ng 2^{poly( )} , kung saan ang poly(n) ay ilang polynomial sa n. Mas pormal, ang isang algorithm ay exponential time kung ang T(n) ay nililimitahan ng O(2^{nk) para sa ilang pare-parehong k. Ref:Wiki.}