<p>Given <span class="math-container">$n$</span> polynomials <span class="math-container">$h_1(x_1,\dots,x_{2n}),\dots,h_{2n}(x_1,\dots,x_{2n})\in\mathbb Z[x_1,\dots,x_{2n}]$</span> where each of <span class="math-container">$h_1(x_1,\dots,x_{2n}),\dots,h_{2n}(x_1,\dots,x_{2n})$</span> is homogeneous of degree <span class="math-container">$d$</span> and <span class="math-container">$r_1,\dots,r_{2n}\in\mathbb Z$</span> what is the complexity of finding common roots over <span class="math-container">$\mathbb Z$</span> for the polynomial system
<span class="math-container">$$h_{2n}(x_1,\dots,x_{2n})=0,\dots,h_{2n}(x_1,\dots,x_{2n})=0?$$</span></p>

<blockquote>
  <p>Is the time and space complexity <span class="math-container">$f(B^d)d^{O(n)}$</span> at some polynomial <span class="math-container">$f$</span> if the roots are bound in <span class="math-container">$B$</span> and we have the condition <span class="math-container">$x_ix_{n+j}=x_jx_{n+i}$</span> at every <span class="math-container">$i,j\in\{1,\dots,n\}$</span>?</p>
</blockquote>

<p>I am unable to find a polynomial system which needs <span class="math-container">$d^{O(n)}$</span> choices with <span class="math-container">$x_ix_{n+j}=x_jx_{n+i}$</span> true. Is there such a polynomial system?</p>

<blockquote>
  <p>I think the complexity might be more like <span class="math-container">$f(B^dnd)$</span>. Is it possible to prove this?</p>
</blockquote>

CC BY-SA 4.0
2019-01-20T00:25:14.727Z
Probably uncomputable. I don't know for sure, but I doubt the homogeneous version of Hilbert's tenth problem has a different answer than the inhomogeneous one.
Joshua Grochow
CC BY-SA 4.0
2019-01-22T05:05:08.933Z
@JoshuaGrochow Please look modifications made.
Turbo
<time-complexity><algebra><polynomials><algebraic-complexity><space-complexity>
Worst case polynomial in elimination theory under rank conditions?
Turbo
# Worst case polynomial in elimination theory under rank conditions?

(Asked by: username_0 on 2019-01-19)

Given $n$ polynomials $h\_1(x\_1,\dots,x\_{2n}),\dots,h\_{2n}(x\_1,\dots,x\_{2n})\in\mathbb Z[x\_1,\dots,x\_{2n}]$ where each of $h\_1(x\_1,\dots,x\_{2n}),\dots,h\_{2n}(x\_1,\dots,x\_{2n})$ is homogeneous of degree $d$ and $r\_1,\dots,r\_{2n}\in\mathbb Z$ what is the complexity of finding common roots over $\mathbb Z$ for the polynomial system
$$h\_{2n}(x\_1,\dots,x\_{2n})=0,\dots,h\_{2n}(x\_1,\dots,x\_{2n})=0?$$

> Is the time and space complexity $f(B^d)d^{O(n)}$ at some polynomial $f$ if the roots are bound in $B$ and we have the condition $x\_ix\_{n+j}=x\_jx\_{n+i}$ at every $i,j\in\{1,\dots,n\}$?

I am unable to find a polynomial system which needs $d^{O(n)}$ choices with $x\_ix\_{n+j}=x\_jx\_{n+i}$ true. Is there such a polynomial system?

> I think the complexity might be more like $f(B^dnd)$. Is it possible to prove this?

**Tags:** time-complexity, algebra, polynomials, algebraic-complexity, space-complexity

> **Comments:**
> **username_1**: Probably uncomputable. I don't know for sure, but I doubt the homogeneous version of Hilbert's tenth problem has a different answer than the inhomogeneous one.  
> **username_0**: @JoshuaGrochow Please look modifications made.  

---

## 0 answers

