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

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

И.А. Лавров.

Аннотация

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

Издание

Труды Института системного программирования РАН, том 12, 2007, стр. 95-122.

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

Для цитирования

И.А. Лавров. Сложность вычислений на абстрактных машинах.. Труды Института системного программирования РАН, том 12, 2007, стр. 95-122. .

Полный текст статьи в формате pdf Вернуться к содержанию тома