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.


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.