Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am interested in the problem of finding a real root of a polynomial equation $f(x)=0$ where $f(x)=\sum_{i=0}^n a_ix^i$. Is it possible to give a reduction, i.e, to compute a different polynomial $g$ in polytime such that $f$ has a real root iff $g$ has a real root in [0,1]$?

share|cite|improve this question
up vote 4 down vote accepted

Not sure if this is the right SE forum for it, but the answer is yes.

I'll give the reduction in two steps:

  1. $f(x)$ has a root iff $h(x)$ has a root in [-1,1] (scaling, i.e. $h(x)=f(\alpha \cdot x)$).
  2. $h(x)$ has a root in [-1,1] iff $g(x)$ has a root in [0,1] (simply define $g(x)=h(\frac{x+1}{2})$).

Let's prove 1:

Let's assume $f(x)$ is of degree $n$ and write it as $f(x) = x^n - a_{n-1} x^{n-1} - ... - a_0$.

If $\alpha \leq 1$, then all of the roots of $f$ in [-1,1] will end up in [-1,1] in $h$.

Let $x$ be a root of $f$ such that $|x|>1$. This means $x^n = a_{n-1} x^{n-1} + ... + a_0$.

since $|x|>1$, $|x^n| > x^{n-1},x^{n-2},...,1$ hence $$|x| \le \text{max}(1, |a_{n-1}| + ... + |a_0|).$$

Define $\alpha = \text{max}(1, |a_{n-1}| + ... + |a_0|)$ and you're done.

share|cite|improve this answer
I think you want $h(x)=f(x / \alpha)$. – Thomas Apr 29 '14 at 17:16
@Thomas - thanks, fixed. – R B Apr 29 '14 at 17:31
Note that this approach can cause a blowup in the height of the coefficients; it's not clear (to me) whether or not this can be done without a substantial blowup in height or degree, though I suspect you need one or the other... – Steven Stadnicki May 1 '14 at 19:17

Here is an alternative to the answer by R B ; It is somewhat simpler, but has the disadvantage of an increase in degree.

Simply take $g(x) = x^{2n}f(x)f(-x)f(1/x)f(-1/x)$.

share|cite|improve this answer
Also, you can make a hybrid of the approaches (simple and not-that-much-higher degree) with: $g(x) = (\frac{x+1}{2})^nf(\frac{x+1}{2})f(\frac{2}{x+1})$. – R B May 1 '14 at 12:04
I think you meant $g(x) = (2x-1)^n f(2x-1) f(1/(2x-1))$, but yes. – Kristoffer Arnsfelt Hansen May 1 '14 at 13:42

Your Answer


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.