5
$\begingroup$

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$?

$\endgroup$
2
  • $\begingroup$ are the matrices PSD? $\endgroup$ Nov 23, 2016 at 0:27
  • $\begingroup$ The matrices are not necessarily PSD $\endgroup$
    – Michael S.
    Nov 23, 2016 at 4:49

1 Answer 1

8
$\begingroup$

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<x_i<-0.9$ holds (in which case we set $u_i$ false) or $0.9<x_i<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<0$; contradiction.

$\endgroup$

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .