Я пытаюсь понять связь между алгоритмической сложностью и сложностью схемы детерминантов и умножения матриц.
Известно, что определитель матрицы может быть вычислен за время ~ O ( M ( n ) ) , где M ( n ) - минимальное время, необходимое для умножения любых двух матриц n × n . Также известно, что наилучшая сложность схем определителей является полиномиальной на глубине O ( log 2 ( n ) ) и экспоненциальной на глубине 3. Но сложность схемы умножения матриц для любой постоянной глубины является лишь полиномиальной.
Почему существует разница в сложности схемы для определителей и умножения матриц, хотя известно, что с точки зрения алгоритма вычисление определителей аналогично умножению матриц? В частности, почему сложности схемы имеют экспоненциальный зазор на глубине ?
Возможно, объяснение простое, но я его не вижу. Есть ли объяснение «строгости»?
Также смотрите в: Наименьшая известная формула для определителя
Я бы сказал, что разрыв в арифметических настройках говорит нам, что умножение матриц по своей сути является гораздо более параллельной задачей, чем определитель. Другими словами, хотя последовательные сложности обеих проблем тесно связаны, их параллельные сложности не так близки друг к другу.
источник