Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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|improve this question

2 Answers 2

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|improve this answer
1  
I think you want $h(x)=f(x / \alpha)$. –  Thomas Apr 29 at 17:16
    
@Thomas - thanks, fixed. –  R B Apr 29 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 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|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 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 at 13:42

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.