# 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))$$ or different?

Is answer to 1. $$O(poly(dtnL))$$ or different?

Is there good reference?

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