# Testing emptiness property complexity in Sum of Squares Proof systems

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.

• 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$.) – Neal Young Jun 22 '20 at 21:40
• (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? – Neal Young Jun 23 '20 at 0:38
• If there is a witness of reasonable length then it will refute emptiness. – VS. Jun 23 '20 at 7:03
• The way $SOS$ works is by producing certifying polynomials and so if the certifying polynomial is polynomial in length the problem is in $NP$. – VS. Jun 23 '20 at 12:36
• 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. – Neal Young Jun 23 '20 at 13:10