Timeline for The word problem in the ring of polynomials
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 10, 2011 at 10:59 | vote | accept | CommunityBot | moved from User.Id=6976 by developer User.Id=69903 | |
| Nov 10, 2011 at 7:33 | answer | added | Greg Kuperberg | timeline score: 5 | |
| Nov 10, 2011 at 3:32 | comment | added | Benjamin Steinberg | Gerhard is correct. See citeseerx.ist.psu.edu/viewdoc/… by Ibarra and Moran. | |
| Nov 10, 2011 at 1:14 | comment | added | Gerhard Paseman | Trivial, perhaps, but not necessarily quick. If Mark has already composed g and the f's, collected terms and no two monomials are additive inverses of one another, then that makes things simpler. All I see so far is g, the f's, and their intended form of composition; it may be that a simple composition is "complicated enough". Also, my suggestion is indeed subpar; I offer it in case nothing better comes along. Gerhard "Ask Me About System Design" Paseman, 2011.11.09 | |
| Nov 8, 2011 at 21:07 | comment | added | Tsuyoshi Ito | @Gerhard: I think that you are talking about the identity test for polynomials given as arithmetic formulas (or circuits). If g were given as an arithmetic formula, the identity test for arithmetic formula could be reduced to the current problem and therefore we could conclude that the current problem is not known to be in NP. But because g is given as a sum of monomials (see Mark’s comment), this argument does not hold. (Note that the identity test for polynomials given as sums of monomials is trivial to solve, so we cannot say anything by reducing it to the current problem.) | |
| Nov 8, 2011 at 1:51 | comment | added | Gerhard Paseman | My memory says there is a quick probabilistic algorithm and no known poly-time algorithms. I recall a problem as trying to determine the rank of a matrix of polynomials, and that plugging in values at random and then evaluating was more successful than an attempt at computing the determinant symbolically, even for small orders. If you get no satisfactory answers, I suggest searching for "symbolic computation of determinants", or words to that effect. Or you could ask Manuel Blum: I heard of it from him. Gerhard "It's Wonderful To Remember Anything" Paseman, 2011.11.07 | |
| Nov 8, 2011 at 0:22 | history | edited | user6976 | CC BY-SA 3.0 |
added 594 characters in body; edited tags; edited tags
|
| Nov 7, 2011 at 23:53 | comment | added | user6976 | @Tsuyoshi: $g$ is given as a sum of monomials, each coefficient and each exponent is in binary. | |
| Nov 7, 2011 at 23:24 | comment | added | Tsuyoshi Ito | How is g given? That is, is it given as an arithmetic circuit, as an arithmetic formula, or as a sum of monomials? If g is given as an arithmetic circuit or an arithmetic formula, I believe that it is not known to be in NP. See also Kabanets and Impagliazzo 2004 (dx.doi.org/10.1007/s00037-004-0182-6). | |
| Nov 7, 2011 at 22:22 | history | asked | user6976 | CC BY-SA 3.0 |