Timeline for Monte Carlo variant of Hilbert's Tenth Problem
Current License: CC BY-SA 3.0
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 20, 2014 at 17:43 | comment | added | Felipe Voloch | The algorithm that always returns false should be pretty good when $d>k$. Slightly better in this range would be to perform a search for solutions up to some power of $C$. For $d \le k$ it's probably better to check local solvability. In that range one expects many equations to have solutions so the always false algorithm won't be so good. I don't know how to get a lower bound that works for all algorithms, i.e., estimate the density of undecidable equations. | |
| Oct 20, 2014 at 16:55 | comment | added | Qiaochu Yuan | I don't know what kind of answer you're expecting. I expect the algorithm that always returns false will do pretty well; maybe it's not even possible to do better than this asymptotically. | |
| Oct 20, 2014 at 16:42 | history | asked | Stefan Kohl♦ | CC BY-SA 3.0 |