<p>Yes, your problem is NP-hard, by reduction from THREE-SATISFIABILITY.</p>

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

<ul>
<li>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$.</li>
<li>We say that $x_i$ represents the Boolean variable $u_i$, and that $-x_i$ represents the negated Boolean variable $\bar{u}_i$.</li>
<li>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$.)</li>
</ul>

<p>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.</p>

<blockquote>
  <p>(Proof of only if): </p>
</blockquote>

<p>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$.</p>

<blockquote>
  <p>(Proof of if):</p>
</blockquote>

<p>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.</p>

CC BY-SA 3.0
2016-11-23T15:47:38.307Z
2016-11-24T15:39:33.367Z
2016-11-24T15:39:33.367Z
Gamow
<p>I am wondering about the complexity of the following problem: </p>

<blockquote>
  <p>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$.<br>
  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). </p>
</blockquote>

<p>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$.</p>

<p>Questions:</p>

<ol>
<li><p>Is this problem NP-hard? </p></li>
<li><p>When $k=1$ there is a randomized algorithm (simply choose a random point). Is there also a randomized algorithm for any $k\ge2$?</p></li>
</ol>

CC BY-SA 3.0
2016-11-23T00:27:09.490Z
are the matrices PSD?
Sasho Nikolov
CC BY-SA 3.0
2016-11-23T04:49:25.497Z
The matrices are not necessarily PSD
Michael S.
<ds.algorithms><np-hardness><randomized-algorithms><polynomials>
Finding a positive point for a collection of polynomials
Michael S.
# Finding a positive point for a collection of polynomials

(Asked by: username_0 on 2016-11-22)

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}) > 0$, $\ldots$, $p\_k({\bf x}) > 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:

1. Is this problem NP-hard?
2. When $k=1$ there is a randomized algorithm (simply choose a random point). Is there also a randomized algorithm for any $k\ge2$?

**Tags:** ds.algorithms, np-hardness, randomized-algorithms, polynomials
> **Comments:**
> **username_1**: are the matrices PSD?  
> **username_0**: The matrices are not necessarily PSD  

---

## 1 answers

### Answer by username_2 on 2016-11-23. Score: 8 | Accepted answer

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>0$ and $1.1^2-x\_i^2>0$ enforce that either $-1.1


---

