On the Complexity of Diophantine Geometry in Low Dimensions

J. Maurice Rojas

We consider the average-case complexity of some otherwise undecidable or open Diophantine problems. More precisely, we show that the following two problems can be solved in the com…