Теоретическая кибернетика

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