# Is the numerical resolution of this huge sparse polynomial system tractable?

I'd like to find numerically a solution to a sparse system of 2000000 polynomial equations of degree 3 with 50000 variables and integer coefficients (or at least to decide whether or not a solution exists).

Question: Is there an algorithm and a supercomputer for which this computation is tractable today?

• Not strictly speaking my field, but my money is on No (or maybe if you work for the NSA). – Federico Poloni Jul 29 '16 at 7:27
• @FedericoPoloni: roughly speaking, what is your estimate for the (space and time) complexity of this computation (and for the capacity of the NSA supercomputers)? – Sebastien Palcoux Jul 29 '16 at 7:53
• It's hard to tell. AFAIK, methods based on Gröbner bases are highly dependent on the specific structure of the equations that you are trying to solve, and the worst-case bounds are astronomically high (exponential or worse). In addition, you can construct a system of equations of the form $x_{i+1}=x_i^3$ for which the number of digits in the solution grows with the dimension, and I don't have particular reasons to believe that the decision problem is easier (apart from obvious loopholes such as "it has no solution modulo 4"). – Federico Poloni Jul 29 '16 at 8:06
• ...and let me add that the general problem of solving diophantine equations is not even algorithmically decidable. So the best you can hope for is a ternary algorithm that returns yes/no/I don't know. – Federico Poloni Jul 29 '16 at 8:12
• Sorry - my last remark applies only to integer solutions; I misread your question. With approximate real solutions it's a different problem. – Federico Poloni Jul 29 '16 at 9:18