Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
add comment

2 Answers 2

up vote 4 down vote accepted

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)$.

share|improve this answer
    
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
2  
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
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.