Complexity of Linear Operators

Пусть дан вектор x булевых переменных, и мы хотим вычислить булев линейный оператор Ax с квадратной булевой матрицей A. Другими словами, для всех строк A мы хотим вычислить дизъюнкцию тех переменных x, для которых соответствующая координата строки равна 1. Вычисление начинается с переменных и за один шаг разрешается вычислить дизъюнкцию двух ранее вычисленных выражений (таким образом, мы строим булеву схему, состоящую из операций дизъюнкции). Если матрица A разреженная (содержит O(n) единиц), оператор легко вычислить за O(n) операций. Мы покажем, что то же самое можно сделать для очень плотных матриц (содержащих O(n) нулей). Этот результат переносится на вычисления операторов над любыми коммутативными полугруппами. Мы также показываем, что аналогичное утверждение неверно для полугрупп, являющихся существенно некоммутативными.