tag:blogger.com,1999:blog-3722233.post5609460581142399437..comments2021-11-26T15:18:15.242-06:00Comments on Computational Complexity: Why is there no (d,n) grid for Hilbert's Tenth Problem?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-3722233.post-70358166675580830802020-06-07T14:35:50.573-05:002020-06-07T14:35:50.573-05:00Here https://mathoverflow.net/questions/207482/alg...Here https://mathoverflow.net/questions/207482/algorithmic-un-solvability-of-diophantine-equations-of-given-degree-with-given it is claimed that the case of cubic equations in 2 variables is decidableBogdanhttps://www.blogger.com/profile/17336734862701615202noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-76030757825506946872020-05-22T19:46:43.211-05:002020-05-22T19:46:43.211-05:00Bill, in connection with your writeup, Lagarias wo...Bill, in connection with your writeup, Lagarias works out explicitly that H10(2,2) is solvable with a relatively simple exponential time algorithm. See https://arxiv.org/abs/math/0611209MSShttps://www.blogger.com/profile/10782385200928123717noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-33798214756412710992020-05-11T08:44:03.716-05:002020-05-11T08:44:03.716-05:00I wonder if you are talking about the right notion...I wonder if you are talking about the right notion of "degree" of a multivariate polynomial (see wikipedia). In your write-up Def 1.4 you say that the degree of (z_1w + z_2)^(2^k) is 2^k but in fact it is 2^(k+1) as the highest term is z_1^(2^k)w^(2^k) which has degree 2^k + 2^k. It would be easy to reduce the maximum degree of a single variable by introducing additional variables and equations, say replace x^8 by x' and x' = a^2, a = b^2, b = x^2. Several equations (e_i = f_i)_(i<n) can be put into one equation (sum_(i<n) (e_i-f_i)^2)=0. All of this is of course well-known.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-68802710851814056382020-05-08T14:55:11.753-05:002020-05-08T14:55:11.753-05:00Here's a nice overview of related questions ht...Here's a nice overview of related questions http://www-math.mit.edu/~poonen/papers/h10_notices.pdfAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-3527393619471436072020-05-05T05:04:38.222-05:002020-05-05T05:04:38.222-05:00If a question is undecidable it just mean the QUES...If a question is undecidable it just mean the QUESTION is wrong, question the question.<br />Anonymousnoreply@blogger.com