Отмена и определитель

9

Алгоритм Берковица обеспечивает схему полиномиального размера с логарифмической глубиной для определителя квадратной матрицы с использованием степеней матрицы. Алгоритм неявно использует отмену. Является ли аннулирование необходимым для получения схемы полиномиального размера с логарифмической или линейной глубиной для расчета детерминанта (и любой возможной наилучшей схемы для постоянной)? Существуют ли полностью экспоненциальные (не просто суперполиномиальные или субэкспоненциальные) нижние оценки для этих задач, использующих схемы без отмены?

circuit-complexity algebraic-complexity permanent arithmetic-circuits determinant Т ....
источник

2

в некотором интуитивном смысле без отмены детерминант - это то же самое, что и перманент

Сашо Николов

11

Да, отмены необходимы, и существуют нижние границы для монотонных и некоммутативных моделей, где отмены невозможны. Смотрите обсуждение в монотонных арифметических схемах . Обзор сложности арифметических схем можно найти в http://www.cs.technion.ac.il/~shpilka/publications/SY10.pdf.

Ноам
источник

1

У кого-то из JIC есть проблема, заключающаяся в том, что монотонные схемы (без -ve констант) не могут вычислить определитель тривиально (так как он содержит -ve коэффи). Определите формальные мономы индуктивно следующим образом: Если

f = g_{1} + g_{2}

$f = g_1 + g_2$ тогда формальные мономы

f

$f$ это союз того

g_{1}

$g_1$ а также

g_{2}

$g_2$ , Если

f = g_{1} \times g_{2}

$f = g_1 \times g_2$ , тогда формальные мономы - это все мономы, полученные путем взятия одного из

g_{1}

$g_1$ и умножить на один из

g_{2}

$g_2$ , Нижняя граница Джеррума-Снира работает до тех пор, пока схема удовлетворяет свойству того, что формальные мономы корня равны ненулевым мономам вычисленного полинома.

Рампрасад

1

Я думаю, что эта статья прямо отвечает на ваш вопрос.

Отмена экспоненциально мощна для вычисления детерминанта

Сенгупта показывает, что даже если вы используете вычитание (следовательно, схема не является монотонной), но до тех пор, пока вы никогда не «отмените» какие-либо вычисленные мономы, тогда вычислитель схемы определит матрицу размера $n \times n$ имеет размер как минимум $n(2^{n-1}-1)$ ,

Thatchaphol
источник

Отмена и определитель

Ответы: