$ x^{100000000000} $ un "tempo polinomiale"?
-
05-11-2019 - |
Domanda
per questo inviare
$ t = x^2 $ significa che il problema è risolvibile nel tempo "polinomio".
per questo inviare
Nella forma
$$ a_ {n} x^{n}+a_ {n-1} x^{n-1}+ dotsb+a_ {2} x^{2}+a_ {1} x+a_ {0} { > Boldsymbol {= 0}} $$
collegare $ n = 100000000000 $ insieme a $ a_n = 1 $ e $ a_k = 0 $ per tutti $ k neq n $
Allora lo vediamo $ x^{100000000000} $ è un polinomio
Non importa se è 2, 3 o un miliardo, purché N sia un numero finito
In questo contesto, fa $ t = x^{100000000000} $ significa ancora che il problema è risolvibile nel tempo "polinomiale"?
Nessuna soluzione corretta
Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a cs.stackexchange