Timeline for Are surjectivity and injectivity of polynomial functions from $\mathbb{Q}^n$ to $\mathbb{Q}$ algorithmically decidable?
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 30, 2013 at 12:47 | comment | added | Igor Rivin | @JoelDavidHamkins yes, in the paper I cite they point this out (since zero-equivalence is undecidable, just as you say). | |
| Jul 30, 2013 at 1:28 | comment | added | Joel David Hamkins | +1. But in this answer, one consider the problem with input having only polynomials with coefficients in $\mathbb{Q}$ (or relax to algebraic), but asking for injectivity/surjectivity of these polynomials over $\mathbb{R}$. If one wants to consider polynomials over $\mathbb{R}$, whose coefficients are given as oracles, then I believe it will be undecidable, because equality of reals given this way is undecidable, and one can reduce $a=b$ to the injectivity and/or surjectivity via the polynomial $p(x)=ax-bx$. | |
| Jul 30, 2013 at 0:56 | comment | added | Igor Rivin | I believe this IS their argument... | |
| Jul 30, 2013 at 0:54 | comment | added | Benjamin Steinberg | For algebraically closed and real closed fields doesn't this follow from decidability of the first order theory? | |
| Jul 29, 2013 at 23:38 | history | answered | Igor Rivin | CC BY-SA 3.0 |