tag:blogger.com,1999:blog-3722233.post6657144417405730404..comments2024-08-02T19:37:12.269-05:00Comments on Computational Complexity: Guest Post on Solving (or trying to) Poly Diophantine Equations by Bogdan GrechukLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-3722233.post-15987972824594043652021-09-12T04:36:16.227-05:002021-09-12T04:36:16.227-05:00Great text Bogdan!Great text Bogdan!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-18555673633496829332021-09-11T14:21:55.695-05:002021-09-11T14:21:55.695-05:00A natural measure of length would be the length of...A natural measure of length would be the length of an efficient binary encoding. That immediately gives an upper bound 2^n on the number of equations of length n bits. I just typed in a description of an elegant encoding which was all wiped out when I hit Preview:-(<br />tromphttps://www.blogger.com/profile/16161842727664839561noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-26968331735255827912021-09-08T12:22:49.531-05:002021-09-08T12:22:49.531-05:00For simplicity, consider monomial of degree d with...For simplicity, consider monomial of degree d with coefficient a. If we do not use "^" notation, how many symbols we need to write it? For example, x^3y^2 is xxxyy, 5 symbols. In general, we need d symbols to write variables. For a coefficient a, it is common in computer science to write it in binary, not in decimal, and then we need about log_2(|a|) symbols. Hence, it is natural to define the length of this monomial M as l(M) = log_2(a)+d. This is nice but not an integer. However, ordering monomials by l(M) is absolutely equivalent to ordering them by 2^{l(M)} = 2^(log_2(|a|)+d) = |a|2^d. Bogdan Grechukhttps://www.blogger.com/profile/01966587783899711586noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-77860135005812340122021-09-07T08:20:32.551-05:002021-09-07T08:20:32.551-05:00Anonymous, in case you missed it, there was a blog...Anonymous, in case you missed it, there was a blog post back in May discussing the meaning of the word "natural" (and by extension, the word "artificial").<br /><br />http://blog.computationalcomplexity.org/2021/05/what-is-natural-question-who-should.html<br /><br />Making all the coefficients positive and plugging in 2 may not be "natural" from the point of view of someone developing the theory of Diophantine equations, but there are people who are interested in the "simplest" Diophantine equations. Of course, one then has to define "simplest" precisely. We want small coefficients and small degree, but how much relative weight do we assign to coefficients versus degree? Substituting 2 for each variable is a simple way to achieve a reasonable balance.<br /><br />At least, that's my guess as to why they chose this measure.Timothy Chowhttps://www.blogger.com/profile/15157353087847193176noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-44246703895677708252021-09-06T14:38:28.243-05:002021-09-06T14:38:28.243-05:00I meant diagonal case. Why only study it?I meant diagonal case. Why only study it?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-84465898801405309062021-09-06T14:37:38.745-05:002021-09-06T14:37:38.745-05:00The notion of height at diagonal case of all coord...The notion of height at diagonal case of all coordinates being 2 is very artificial.Anonymousnoreply@blogger.com