Katika nadharia ya uchangamano wa hesabu, upunguzaji wa muda wa polynomia ni njia ya kutatua tatizo moja kwa kutumia jingine. Upunguzaji wa muda wa polynomia hutumiwa mara kwa mara katika nadharia ya uchangamano kufafanua aina zote mbili za uchangamano na matatizo kamili kwa madarasa hayo. …
Ni wakati gani unachukuliwa kuwa wa polynomial?
Algoriti inasemekana kuwa ya wakati wa polinomia ikiwa muda wake wa kufanya kazi ni wa juu zaidi unaopakana na usemi wa polinomia katika saizi ya ingizo la algoriti, yaani, T(n)=O(nk) kwa kiasi chanya chanya k.
Unajuaje kama kitu ni wakati wa polynomial?
Majibu 3. Algoriti ni ya polinomia (ina muda wa uendeshaji wa polinomia) ikiwa kwa k, C>0, muda wake wa kutumia pembejeo za saizi n ni Cnk zaidi. Kwa usawa, algoriti ni ya aina nyingi ikiwa kwa baadhi ya k>0, wakati wake wa kutumia pembejeo za saizi n ni O(nk).
Je, nini kitatokea ikiwa kupunguzwa kunaruhusiwa katika muda mfupi zaidi?
Ikiwa upunguzaji unaruhusiwa muda wa ziada, basi inaweza kutatua tatizo la awali kikamilifu na kutoa mfano mdogo wa tatizo lengwa Hii inamaanisha kuwa kila tatizo katika NP linaweza kupunguzwa kwa kila tatizo lingine kwa aina kama hizi za upunguzaji, kwa hivyo kila tatizo katika NP ni NP-kamili kwa upunguzaji wa muda wa kielelezo.
Algoriti ya kielelezo ni nini?
Algoriti inasemekana kuwa muda wa mwonekano, ikiwa T(n) inapakana na 2poly( ) , ambapo aina nyingi(n) ni nyingi katika n. Rasmi zaidi, algoriti ni wakati wa kielelezo ikiwa T(n) inafungwa na O(2nk) kwa k. Ref:Wiki isiyobadilika.
