RUS  ENG
Полная версия
ЖУРНАЛЫ // Препринты Института прикладной математики им. М. В. Келдыша РАН // Архив

Препринты ИПМ им. М. В. Келдыша, 2001, 017 (Mi ipmp1069)

Алгебраические методы определения сложности

А. В. Ворожцов


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



© МИАН, 2024