2 ms·
> Later on, I reduced another interviewer's search problem to a polynomial equation that had integer roots when a solution existed well, you can reduce any com
by kpierre 15y ago
> Later on, I reduced another interviewer's search problem to a polynomial equation that had integer roots when a solution existed
well, you can reduce any computable problem to that form
see http://en.wikipedia.org/wiki/10th_Hilbert_problem http://en.wikipedia.org/wiki/10th_Hilbert_problem
- jules 15y agoFor the single variable case there is an algorithm: http://en.wikipedia.org/wiki/Rational_root_theorem http://en.wikipedia.org/wiki/Rational_root_theorem Whether it is a fast algorithm depends heavily on the sizes of the first and last coefficients, as you have to factorize them.