4
$\begingroup$

Take the set $$\mathcal T=\{f_1(x_1,\dots,x_n)=\dots=f_m(x_1,\dots,x_n)=0, h_1(x_1,\dots,x_n)\geq a_1,\dots,h_t(x_1,\dots,x_n)\geq a_t\}$$ where $$h_1(x_1,\dots,x_n),\dots,h_t(x_1,\dots,x_n)\in\mathbb Z[x_1,\dots,x_n]$$ are linear homogeneous polynomials with $a_1,\dots,a_t\in\mathbb Z$ and $$f_1(x_1,\dots,x_n),\dots,f_n(x_1,\dots,x_n)\in\mathbb Z[x_1,\dots,x_n]$$ are degree $d$-homogeneous polynomials.

We can test if $\mathcal T=\emptyset$ by Sum Of Squares proof system.

What is the complexity if $d$ and $t$ are $O(1)$ and $m\geq n$ holds?

Note since $m\geq n$ holds $\mathcal T=\emptyset$ almost always.

I am looking for general upper bounds on:

  1. Number of bits in certifying polynomials

  2. Degree of certifying polynomias

  3. Time to get the certificates in SDPs.

in terms of the degree $d$ of the polynomials $f_i(x_1,\dots,x_n)$, $t$ the number of polynomials $h_i(x_1,\dots,x_n)$, $m$ the number of polynomials $f_i(x_1,\dots,x_n)$ and $n$ the number of variables in the polynomials and also $L$ the total number of bits to represent the polynomial coefficients of $f_i(x_1,\dots,x_n)$, $h_i(x_1,\dots,x_n)$?

Is answer to 3. $O((dt)^npoly(dtnL))$ where $L$ is number of bits to encode polynomials $f_1,\dots,f_n,h_1,\dots,h_t$ or much higher?

Is answer to 2. $O(polylog(dtnL))$ and is answer to 1. $O(poly(dtnL))$?

Is there good reference on these topics?

Updates Note testing 'Is $\mathcal T\cap\mathbb Z^n=\emptyset$?' is in $coNP$ and perhaps it is in $NP$ as well.

Improve this question
$\endgroup$
7
  • $\begingroup$ Testing whether a given equation $f(x_1, x_2, \ldots, x_n) = 0$ has a solution, where $f$ is a quadratic polynomial, is easily shown to be NP-complete (e.g. here). Can't you easily reduce this to your question by converting $f$ into a degree-2 homogenous polynomial by the addition of an additional variable $x_{n+1}$ (used to multiply terms as necessary), along with two linear constraints $x_{n+1} \ge 1$ and $-x_{n+1} \ge -1$? (Work around the restriction $m\ge n$ by duplicating $f$.) $\endgroup$ – Neal Young Jun 22 '20 at 21:40
  • $\begingroup$ (continued) So I think your problem is unlikely to be in NP$\cap$co-NP, as you suggest in your Updates line. By the way, could you clarify what you mean by "certifying polynomials" and "certificates" in Items 1-3? $\endgroup$ – Neal Young Jun 23 '20 at 0:38
  • $\begingroup$ If there is a witness of reasonable length then it will refute emptiness. $\endgroup$ – VS. Jun 23 '20 at 7:03
  • $\begingroup$ The way $SOS$ works is by producing certifying polynomials and so if the certifying polynomial is polynomial in length the problem is in $NP$. $\endgroup$ – VS. Jun 23 '20 at 12:36
  • $\begingroup$ For those such as myself not familiar with SOS, the following introduction may help: Proofs, beliefs, and algorithms through the lens of sum-of-squares by Barak and Steurer. $\endgroup$ – Neal Young Jun 23 '20 at 13:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.