# Do the polynomials in “polynomial time” have integer, real or complex coefficients?

This is probably a very basic question but do the polynomials in "polynomial time" have integer, real or complex coefficients?

Everywhere I looked it just says "polynomial expression". I am guessing the polynomial must have integer coefficients?

-

When people say polynomial time, they mean that the time has polynomial growth, that is if we denote the time by $T(n)$, then $T(n) = O(n^c)$ for some real $c$. We get the same definition if we only allow integer $c$. Since $T(n)$ is real-valued, it wouldn't make sense to consider complex polynomials here.

The exact running time need not actually be a polynomial. For example, an algorithm running in time $n\log n$ (exactly) still runs in polynomial time, since (for example) $n\log n = O(n^2)$.

-
For example, here: en.wikipedia.org/wiki/NP_(complexity)#Formal_definition, when they say "there exists polynomials", do they mean polynomial expressions with integer coefficients? –  Jean Valjean Mar 2 at 1:56
The definition in Wikipedia is wrong, unless by "running in time $p(|x|)$" they actually mean "running in time at most $p(|x|)$". In the latter case, you can choose a polynomial with coefficients over a (non-trivial) subring of the reals of your choice. The resulting definitions will be equivalent, indeed, equivalent to the definition I gave in the answer. (Exercise.) –  Yuval Filmus Mar 2 at 1:58
The complex numbers aren't ordered, and the polynomials used in complexity theory are supposed to order sets according to their "difficulty". Maybe that'll help you remember why complex coefficients (and/or polynomials over the complex numbers) aren't useful in complexity bounds. –  G. Bach Mar 2 at 2:38
By the way, the alternative definition in Wikipedia (using NTIME) is exactly the one appearing in the answer. –  Yuval Filmus Mar 2 at 2:40

What would it even mean to say that "The Turing machine $M$ runs in time at most $(3i+2)n^3$ when given input of length $n$"? So, clearly, the coefficients are real.

-