Сложность вычислений на абстрактных машинах.

Сложность вычислений на абстрактных машинах.

И.А. Лавров.

Abstract

В статье освещены важные аспекты классической теории алгоритмов и теории сложности вычислений. Показано, что ряд подходов к формализации понятия сложности вычислений неадекватно отражает данное понятие. Более последовательным представляется построение различных иерархий классов сложности. С помощью подобных классов удается локализовать уровни сложности ряда классических математических задач.

Edition

Proceedings of the Institute for System Programming, vol. 12 (in Russian), 2007, Стр. 95-122.

ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

For citation

И.А. Лавров. Сложность вычислений на абстрактных машинах.. Proceedings of the Institute for System Programming, vol. 12 (in Russian), 2007, Стр. 95-122. .

Full text of the paper in pdf (in Russian) Back to the contents of the volume