<p>Take the set <span class="math-container">$$\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\}$$</span> where <span class="math-container">$$h_1(x_1,\dots,x_n),\dots,h_t(x_1,\dots,x_n)\in\mathbb Z[x_1,\dots,x_n]$$</span> are linear homogeneous polynomials with <span class="math-container">$a_1,\dots,a_t\in\mathbb Z$</span> and <span class="math-container">$$f_1(x_1,\dots,x_n),\dots,f_n(x_1,\dots,x_n)\in\mathbb Z[x_1,\dots,x_n]$$</span> are degree <span class="math-container">$d$</span>-homogeneous polynomials.</p>
<p>We can test if <span class="math-container">$\mathcal T=\emptyset$</span> by Sum Of Squares proof system.</p>
<blockquote>
<p>What is the complexity if <span class="math-container">$d$</span> and <span class="math-container">$t$</span> are <span class="math-container">$O(1)$</span> and <span class="math-container">$m\geq n$</span> holds?</p>
</blockquote>
<p>Note since <span class="math-container">$m\geq n$</span> holds <span class="math-container">$\mathcal T=\emptyset$</span> almost always.</p>
<p>I am looking for general upper bounds on:</p>
<ol>
<li><p>Number of bits in certifying polynomials</p>
</li>
<li><p>Degree of certifying polynomias</p>
</li>
<li><p>Time to get the certificates in SDPs.</p>
</li>
</ol>
<p>in terms of the degree <span class="math-container">$d$</span> of the polynomials <span class="math-container">$f_i(x_1,\dots,x_n)$</span>, <span class="math-container">$t$</span> the number of polynomials <span class="math-container">$h_i(x_1,\dots,x_n)$</span>, <span class="math-container">$m$</span> the number of polynomials <span class="math-container">$f_i(x_1,\dots,x_n)$</span> and <span class="math-container">$n$</span> the number of variables in the polynomials and also <span class="math-container">$L$</span> the total number of bits to represent the polynomial coefficients of <span class="math-container">$f_i(x_1,\dots,x_n)$</span>, <span class="math-container">$h_i(x_1,\dots,x_n)$</span>?</p>
<blockquote>
<p>Is answer to 3. <span class="math-container">$O((dt)^npoly(dtnL))$</span> where <span class="math-container">$L$</span> is number of bits to encode polynomials <span class="math-container">$f_1,\dots,f_n,h_1,\dots,h_t$</span> or much higher?</p>
<p>Is answer to 2. <span class="math-container">$O(polylog(dtnL))$</span> and is answer to 1. <span class="math-container">$O(poly(dtnL))$</span>?</p>
<p>Is there good reference on these topics?</p>
</blockquote>
<p><strong>Updates</strong> Note testing 'Is <span class="math-container">$\mathcal T\cap\mathbb Z^n=\emptyset$</span>?' is in <span class="math-container">$coNP$</span> and perhaps it is in <span class="math-container">$NP$</span> as well.</p>

CC BY-SA 4.0
2020-06-22T21:40:00.937Z
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](https://cs.stackexchange.com/questions/79339/np-completeness-of-solving-quadratic-equations-over-mathbbz-2)).  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
CC BY-SA 4.0
2020-06-23T00:38:18.077Z
(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
CC BY-SA 4.0
2020-06-23T07:03:11.647Z
If there is a witness of reasonable length then it will refute emptiness.
VS.
CC BY-SA 4.0
2020-06-23T12:36:57.557Z
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.
CC BY-SA 4.0
2020-06-23T13:10:23.560Z
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](https://www.sumofsquares.org/public/index.html) by Barak and Steurer.
Neal Young
CC BY-SA 4.0
2020-06-23T16:05:07.857Z
VS, isn't it the case that even for $d=t=2$ your problem is co-NP hard, so is very unlikely to be in NP (which it would be if it had the poly-size certificates you ask about in Item 1)?
Neal Young
CC BY-SA 4.0
2020-06-23T16:26:19.070Z
Is there a confusion in your definition of $\mathcal T$?  As defined $\mathcal T$ is a non-empty set of constraints, and you never have $\mathcal T = \emptyset$, which is the property you say you want to determine...  Presumably you want to determine whether the constraints in $\mathcal T$ have no feasible solution, and for that you'd need to define $\mathcal T$ as the set of feasible solutions to the given constraints.
Neal Young
<cc.complexity-theory><polynomials><proof-complexity><semidefinite-programming><sum-of-squares>
Testing emptiness property complexity in Sum of Squares Proof systems
VS.
# Testing emptiness property complexity in Sum of Squares Proof systems

(Asked by: username_0 on 2019-03-22)

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.

**Tags:** cc.complexity-theory, polynomials, proof-complexity, semidefinite-programming, sum-of-squares
> **Comments:**
> **username_1**: 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](https://cs.stackexchange.com/questions/79339/np-completeness-of-solving-quadratic-equations-over-mathbbz-2)).  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$.)  
> **username_1**: (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?  
> **username_0**: If there is a witness of reasonable length then it will refute emptiness.  
> **username_0**: The way $SOS$ works is by producing certifying polynomials and so if the certifying polynomial is polynomial in length the problem is in $NP$.  
> **username_1**: 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](https://www.sumofsquares.org/public/index.html) by Barak and Steurer.  
> **username_1**: VS, isn't it the case that even for $d=t=2$ your problem is co-NP hard, so is very unlikely to be in NP (which it would be if it had the poly-size certificates you ask about in Item 1)?  
> **username_1**: Is there a confusion in your definition of $\mathcal T$?  As defined $\mathcal T$ is a non-empty set of constraints, and you never have $\mathcal T = \emptyset$, which is the property you say you want to determine...  Presumably you want to determine whether the constraints in $\mathcal T$ have no feasible solution, and for that you'd need to define $\mathcal T$ as the set of feasible solutions to the given constraints.  

---

## 0 answers

