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:
Number of bits in certifying polynomials
Degree of certifying polynomias
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.
