Al menos en principio, una solución es el siguiente resultado, debido a J. Sylvester:
Teorema (Sylvester). Para cada número natural $n \geq 2$ existe un conjunto de más de $n-1$ polinomios con coeficientes enteros $$R_{n, \, 1}(X_1, \ldots, X_n), \ldots, R_{n, \, k(n)}(X_1, \ldots, X_n)$$
tal que el monic real de los polinomios de grado $n$ $$P(x)=x^n+a_{1}x^{n-1}+ \cdots + a_n$$
tener sólo las raíces reales son precisamente aquellos para los que $$R_{n, \, 1}(a_1, \ldots, a_n) \geq 0, \ldots, R_{n, \, k(n)}(a_1, \ldots, a_n) \geq 0.$$
Esto puede ser visto como una generalización del hecho bien conocido de que un verdadero cuadrática monic polinomio $x^2+a_1x+a_2$ sólo tiene raíces reales si y solo si su discriminante $$D_2(1, \, a_1, \, a_2)=a_1^2-4 a_2$$
es no negativo. De hecho, para todos los enteros positivos $n$ tenemos $$R_{n, \, 1}(a_1, \ldots, a_n) = D_n(1, \, a_1, \ldots, a_n),$$
donde $D_n$ es el discriminante de $P(x)$, mientras que los otros polinomios $R_{n, \,i}$ puede ser explícitamente calculada en términos de determinantes extraído de la matriz de Sylvester $P$ e $P'$.
Así, con el fin de responder a su pregunta, se debe verificar si $$R_{n, \, 1}(\epsilon_1 a_1, \ldots, \epsilon_n a_n) \geq 0, \ldots, R_{n, \, k(n)}(\epsilon_1 a_1, \ldots, \epsilon_n a_n) \geq 0$$
para algunos la elección de $\epsilon_1, \ldots, \epsilon_n \in \{-1, \, 1 \}.$ Desde el punto de vista computacional, el problema es que el número de no-cero de los coeficientes en nuestro polinomios aumenta rápidamente con el grado: por ejemplo, $R_{9, \,1}=D_9$ ha $26095$ términos.
Para más detalles, ver
C. Niculescu, L. E. Persson: Funciones Convexas y sus Aplicaciones: Un Enfoque Contemporáneo, el Apéndice B.
