tag:blogger.com,1999:blog-3722233.post5609460581142399437..comments2020-05-25T04:05:03.716-04:00Comments on Computational Complexity: Why is there no (d,n) grid for Hilbert's Tenth Problem?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-3722233.post-76030757825506946872020-05-22T20:46:43.211-04:002020-05-22T20:46:43.211-04: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-11T09:44:03.716-04:002020-05-11T09:44:03.716-04: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-08T15:55:11.753-04:002020-05-08T15:55:11.753-04: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-05T06:04:38.222-04:002020-05-05T06:04:38.222-04: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