Abstract:
Problems of solving of linear Diophantine equations and inequalities, of constructing of Diophantine approximations and of solving of quadratic Diophantine equations are considered from the view of complexity theory. Various known algorithms for solving these problems especially Euclidian algorithms for matrices, Lenatra's algorithm and Voronoi's algorithm are considered and their time complexity functions are evaluated. Machine independent variant of complexity theory is described. Some open problems are formulated.
