Finding a positive point for a collection of polynomials I am wondering about the complexity of the following problem: 


  Given $k$ polynomials $p_1(x_1, \ldots, x_n)$, $p_2(x_1, \ldots, x_n)$,
  $\ldots$, $p_k(x_1, \ldots, x_n)$ over the $n$ real variables $x_1,\ldots,x_n$.
  Find a point ${\bf x} = (x_1, \ldots, x_n) \in \mathbb{R}^n$ such that $p_1({\bf x}) &gt; 0$, $\ldots$, $p_k({\bf x}) &gt; 0$ (or declare that no such point exists). 


Let us furthermore assume that each polynomial is given in the form $p_i(x) = \det(A_0^i + \sum_k x_k A_k^i)$, where we are given the matrices $A_0^i, \ldots, A_k^i$.

Questions:


Is this problem NP-hard? 
When $k=1$ there is a randomized algorithm (simply choose a random point). Is there also a randomized algorithm for any $k\ge2$?
Yes, your problem is NP-hard, by reduction from THREE-SATISFIABILITY.


  THREE-SATISFIABILITY:
  Instance: Boolean variables $u_1,\ldots,u_n$; clauses $c_1,\ldots,c_m$ of length three over the $u_i$
  Question: Does there exist a truth setting of the $u_i$ that makes all clauses $u_j$ true?



For every Boolean variable $u_i$, introduce a corresponding real variable $x_i$ together with the two polynomials $x_i^2-0.9^2$ and $1.1^2-x_i^2$.
We say that $x_i$ represents the Boolean variable $u_i$, and that $-x_i$ represents the negated Boolean variable $\bar{u}_i$.
For every clause $c_j$, introduce one corresponding polynomial that is the sum of the real variables corresponding to the three literals plus $1.1$.
(For instance, the clause $u_a\lor\bar u_b\lor\bar u_c$ is represented by the corresponding polynomial $x_a-x_b-x_c+1.1$.)


We claim that the THREE-SATISFIABILITY instance has answer YES, if and only if there exists a positive point for the constructed set of polynomials.


  (Proof of only if): 


Consider a satisfying truth setting for the THREE-SATISFIABILITY instance. If $u_i$ is true, then set $x_i=1$, and if $u_i$ is false, then set $x_i=-1$. This makes all polynomials $x_i^2-0.9^2$ and $1.1^2-x_i^2$ positive. Since every clause contains at least one true literal, the sum of the corresponding three real variables is at least $-1-1+1=-1$, so that the corresponding polynomial yields a value of at least $0.1$.


  (Proof of if):


Consider a positive point for the constructed set of polynomials. Then $x_i^2-0.9^2&gt;0$ and $1.1^2-x_i^2&gt;0$ enforce that either $-1.1&lt;x_i&lt;-0.9$ holds (in which case we set $u_i$ false) or $0.9&lt;x_i&lt;1.1$ holds (in which case we set $u_i$ true). Suppose for the sake of contradiction that under the constructed truth setting, some clause $c_j$ would contain three false literals. Then each of the three corresponding real variables is $\le-0.9$. Then the polynomial corresponding to that clause has value at most $-0.9-0.9-0.9+1.1&lt;0$; contradiction.