A Formal Proof of Complexity Bounds on Diophantine Equations

Re:A Formal Proof of Complexity Bounds on Diophantine Equations by btilly on Friday May 23, 2025 @06:22PM (#44077150)

I found https://x.com/gm8xx8/status/1925768687618773079 to be a little more understandable summary of what was actually shown.

Any Diophantine equation can be reduced to one of at most 11 variables and degree at most around 10^63. No algorithm can decide solvability in rational numbers for this class of Diophantine equations.

[ Parent | on HN ]

Re:A Formal Proof of Complexity Bounds on Diophantine Equations by throwaway81523 on Friday May 23, 2025 @09:02PM (#44078001)

That sounds like the coefficients might have to be arbitrarily large. Otherwise all DE's could reduce to a finite set of them, impossible via the MRDP theorem. So it's not so easy to call that bounded complexity.

[ Parent | on HN ]