Let $\mathbb F\in\{\mathbb R, \mathbb C\}$ the field of real or complex numbers. Then [1, page 22 in the middle] claims that the following equation can easily be solved in deterministic polynomial time: $$ \sum_{i=1}^n a_ix_i^2=b$$ with $a_i, b\in\mathbb F$. Some discussion suggests, that the algorithmical model assumed in the paper is that of a machine that can perform field operations in one step.
My question is: What is the algorithm? Is it multidimensional Newton? That would be weird because this algorithm only converges (in some cases) and does not give an exact solution. I'm quite unused to computational models over fields like the reals or complex numbers and maybe for someone who is more experienced this is cristal-clear?
[1] Agrawal & Saxena, On the complexity of cubic forms, 2006.
Asked By : born
Answered By : Yuval Filmus
We assume that we are allowed to take square roots in $\mathbb{F}$.
$\mathbb{F} = \mathbb{C}$: If $b = 0$ then $x_1 = \cdots = x_n = 0$ is a solution. If $b \neq 0$ and $a_1 = \cdots = a_n = 0$ then there is no solution. Otherwise, let $a_i \neq 0$, and then a solution is $x_i = \sqrt{b/a_i}$ and $x_j = 0$ for $j \neq i$.
$\mathbb{F} = \mathbb{R}$: If $b = 0$ then $x_1 = \cdots = x_n = 0$ is a solution. Otherwise, without loss of generality assume that $b > 0$ (otherwise, multiply all of $b,a_1,\ldots,a_n$ by $-1$). If $a_i \leq 0$ for all $i$ there is no solution. Otherwise, let $a_i > 0$, and then a solution is $x_i = \sqrt{b/a_i}$ and $x_j = 0$ for $j \neq i$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/2697
0 comments:
Post a Comment
Let us know your responses and feedback