Rešitev: Ničla polinoma

Iz MaFiRaWiki

Naloga: Ničla polinoma

Kot že vemo, so v razredu P odločitveni problemi, ki so rešljivi v polinomskem času na determinističnem Turingovem stroju, v razredu NP pa odločitveni problemi, rešljivi v polinomskem času na nedeterminističnem Turingovem stroju.

Najprej se vprašamo, če je to problem v odločitveni obliki:

Podano: koeficienti polinoma a0,a1,...,an
Vprašanje: Ali je a0 + a1*x0+...+an*x_0^n = 0 ?
Odgovor: Da ali Ne.
Sedaj se spomnemo Hornerjevega algoritma in problem zapišemo v obliki a0 + x * (a1 + x * (a2 + x * (a3 + ... + x * (a(n − 1) + x * an)...) = 0.
Ta problem je rešljiv na determinističnem Turingovem stroju.

Preveriti še moramo, da je rešljiv v polinomskem času:

Časovna zahtevnost je O(n), če štejemo množenja in O(m2) (m dolžina x) n-krat pri vsakem množenju. V obeh primerih je odvisnost polinomska.

Ta problem je torej v P.

Glej tudi

Osebna orodja