tag:blogger.com,1999:blog-3722233.post8975826682758317937..comments2024-11-14T17:42:16.782-06:00Comments on Computational Complexity: When are both x^2+3y and y^2+3x both squares, and a more general questionLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-3722233.post-59190702374096052242020-09-13T03:37:46.105-05:002020-09-13T03:37:46.105-05:00Lots of languages have libraries to do arbitrary p...Lots of languages have libraries to do arbitrary precision (integer) math, or have it build in.<br /><br />I also made a program searching for solutions, going all the way up to 100,000,000, using arbitrary big integers to avoid any precision errors: https://github.com/Abigail/Misc/blob/master/xx3yAbigailnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-49608884812356423652020-09-11T16:46:17.909-05:002020-09-11T16:46:17.909-05:00New Optimization Era:
https://www.aimsciences.org...New Optimization Era:<br /><br />https://www.aimsciences.org/article/doi/10.3934/naco.2019051Yuly Shipilevskyhttps://www.blogger.com/profile/13699450530150796472noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-9411511547678819842020-09-10T18:47:22.016-05:002020-09-10T18:47:22.016-05:00I would be curious if the program would give incor...I would be curious if the program would give incorrect results if take up to larger values to check due to precision errors.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-3116455456341917482020-09-10T17:31:45.300-05:002020-09-10T17:31:45.300-05:00I'm not an expert, but I think that the genera...I'm not an expert, but I think that the general question (2) is "a little bit" harder than the one in the last post because it falls in the "neighbourhood" of the Hilbert's 10th problem.<br /><br />We know that:<br />- deciding if a polynomial equation in 11 variables has integer solutions is undecidable<br />- deciding if a polynomial equation in 1 variable has integer solutions is decidable<br /><br />But I think that everything in between is unknown (even for the 2 variables case).<br /><br />And deciding whether p in Z[x1,x2] has integer solutions (p(x1,x2)=0) can be reduced to your problem:<br /><br />p' = 1 - p * p <br />q' = p'<br /><br />p'(x1,x2), q'(x1,x2) are both squares iif p(x1,x2)=0Marzio De Biasihttps://www.blogger.com/profile/18441670787376943932noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-30244533368120382812020-09-10T15:20:11.200-05:002020-09-10T15:20:11.200-05:00Surely you are correct, or were correct, as I have...Surely you are correct, or were correct, as I have fixed it.<br /><br />thx!gasarchhttps://www.blogger.com/profile/03004932739846901628noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-53512449502383868902020-09-10T15:15:46.481-05:002020-09-10T15:15:46.481-05:00Surely a typo in the title?Surely a typo in the title?Jim Hefferonhttps://www.blogger.com/profile/09292836035665054384noreply@blogger.com