---

Hvad er forskellen på polynomiel og ikke-polynomiel?

---

saneman wrote:
> Hvad er forskellen på polynomiel og ikke-polynomiel?

Med forbehold for at jeg har misforstået dit spørgsmål, eller at jeg
ikke aner hvad jeg skriver om:

Noget udvikler sig polynomielt hvis det kan beskrives af en formel på
følgende form:
a_0*x^0 + a_1*x^1 + a_2*x^2 + ... + a_n*x^n

Hvis man snakker om en algoritmes tidskompleksitet, er den "polynomiel"
hvis det antal af tidsenheder den bruger på at beregne en opgave af
størrelsen 'n' har som den mest betydende faktor n opløftet i en
konstant. Med andre ord: så må beregningstiden ikke vokse hurtigere end
n opløftet i den *samme konstant* uanset n's størrelse (og hvor vi
ignorerer eventuelle mindrebetydende faktorer).

Et problem som siges kun* at have en ikke-polynomiel løsning mht. f.eks.
tidskompleksitet, kan ikke begrænse sig til at bruge n^a tid (hvor a er
en konstant).

* Det er et af datalogiens store åbne spørgsmål om en klasse af
ikke-polynomielle algoritmer kaldet NP-complete, virkelig er ikke
"hurtigt" kan "omskrives" til en form hvor de har en polynomiel løsning.