MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).
show/hide this revision's text 4 deleted 341 characters in body

Question1 Is the problem of finding a rational root of $f(x)$ in P for every $n$ (say, for $n=5$)?

Update 1 After I posted the question, I noticed an answer by Robert Israel to the previous question (of Joseph O'Rourke). That could give an answer to my question but I am still not sure how one can avoid factoring numbers $a_0,a_n$.

Question

Update 2 Robert Israel's explanations (more closely related to the original question). Suppose see his comment here ) convince me that all roots his algorithm of $f$ are rational. Can one find a rational root by the following procedure

Step 1. Find checking whether a number $p_1$ that is polynomially dependent on the coefficients of $f$ (say, the discriminant of $f$) and check if $p_1$ polynomial has a rational root $b_1$ of degree $k_1\le n$(all roots rational) runs in polynomial time.

Step

I removed Question 2 . Find a number $p_2$ so that is polynomially dependent on the coefficients of $f$ and $b_1$ and check if it has a rational root of degree $k_2\le n$. I can accept Michael Stoll's answer. ...

The number $p_m$ ($m\le n$) is a rational root of $f$.

Note that existence of such I will post Question 2 as a procedure does not contradict unsolvability of the symmetric group $S_n$, $n\ge 5$, because we assume that the Galois group of $f$ is trivialseparate question.

show/hide this revision's text 3 added question 2.

This is inspired by this question. Let $f(x)=a_nx^n+...+a_0$ be a polynomial with rational coefficients. The sandard procedure of finding a rational root $p/q$ involves checking all $p$ that divide $a_0$ and all $q$ that divide $a_0$. This is not very complicated but involves factoring $a_0$ and $a_n$. The factoring problem is not known to be in P. If $n\le 4$, then the fact that the group $S_4$ is solvable and the well known formulas for roots of polynomials of degree $\le 4$ give easy polynomial time algorithm of finding rational roots.

Question 1 Is the problem of finding a rational root of $f(x)$ in P for every $n$ (say, for $n=5$)?

Update After I posted the question, I noticed an answer by Robert Israel to the previous question (of Joseph O'Rourke). That could give an answer to my question but I am still not sure how one can avoid factoring numbers $a_0,a_n$.

Question 2 (more closely related to the original question). Suppose that all roots of $f$ are rational. Can one find a rational root by the following procedure

Step 1. Find a number $p_1$ that is polynomially dependent on the coefficients of $f$ (say, the discriminant of $f$) and check if $p_1$ has a rational root $b_1$ of degree $k_1\le n$.

Step 2. Find a number $p_2$ that is polynomially dependent on the coefficients of $f$ and $b_1$ and check if it has a rational root of degree $k_2\le n$.

....

The number $p_m$ ($m\le n$) is a rational root of $f$.

Note that existence of such a procedure does not contradict unsolvability of the symmetric group $S_n$, $n\ge 5$, because we assume that the Galois group of $f$ is trivial.

show/hide this revision's text 2 added 340 characters in body

This is inspired by this question. Let $f(x)=a_nx^n+...+a_0$ be a polynomial with rational coefficients. The sandard procedure of finding a rational root $p/q$ involves checking all $p$ that divide $a_0$ and all $q$ that divide $a_0$. This is not very complicated but involves factoring $a_0$ and $a_n$. The factoring problem is not known to be in P. If $n\le 4$, then the fact that the group $S_4$ is solvable and the well known formulas for roots of polynomials of degree $\le 4$ give easy polynomial time algorithm of finding rational roots.

Question Is the problem of finding a rational root of $f(x)$ in P for every $n$ (say, for $n=5$)?

Update After I posted the question, I noticed an answer by Robert Israel to the previous question (of Joseph O'Rourke). That could give an answer to my question but I am still not sure how one can avoid factoring numbers $a_0,a_n$.

show/hide this revision's text 1