Аннотация:
Для четырех задач теории чисел – решения линейных диофантовых уравнений и неравенств, отыскания диофантовых приближений и решения квадратных диофантовых уравнений дается анализ сложности известных алгоритмов решения. Сравнение различных алгоритмов производится на основе их временной сложности. Особо подчеркивается связь временной сложности с размерами промежуточных чисел. Приводится машинно независимое описание классов сложности, формулируются открытые задачи.
