Какова самая общая структура, на которой проверка матричного продукта может быть выполнена за

18

В 1979 году Фрейвалдс показал, что верификация матричных произведений по любому полю может быть выполнена за рандомизированное время . Более формально, учитывая три матрицы A, B и C, с записями из поля F, проблема проверки, имеет ли AB = C случайный O ( n 2 ) алгоритм времени.O(n2)O(n2)

Это интересно, потому что самый быстрый известный алгоритм для умножения матриц медленнее, чем этот, поэтому проверка, если AB = C быстрее, чем вычисление C.

Я хочу знать, что является наиболее общей алгебраической структурой, для которой верификация матричного произведения все еще имеет алгоритм времени (рандомизированный). Поскольку оригинальный алгоритм работает над всеми полями, я думаю, что он работает и над всеми интегральными областями.O(n2)

Наилучший ответ, который я смог найти на этот вопрос, был в « Субкубических эквивалентностях между задачами пути, матрицы и треугольника» , где говорится, что «проверка матричного произведения по кольцам может быть выполнена за рандомизированное время [BK95]». ([BK95]: М. Блюм и С. Каннан. Разработка программ, которые проверяют их работу. J. ACM, 42 (1): 269–291, 1995.)O(n2)

Во-первых, являются ли кольца самой общей структурой, в которой эта задача имеет рандомизированный алгоритм? Во-вторых, я не мог видеть, как результаты [BK95] показывают алгоритм времени O ( n 2 ) для всех колец. Может кто-нибудь объяснить, как это работает?O(n2)O(n2)

Робин Котари
источник
Глупый вопрос: очевидно ли, что детерминированная проверка так же сложна, как умножение? Что делать, если вам дают не только A, B и C, но и компактный сертификат; это помогает?
Юкка Суомела
@Jukka: я полагаю, что лучший детерминистический алгоритм для этой задачи не быстрее, чем умножение матриц, но я не знаю, есть ли причина, почему так должно быть. Что касается второго вопроса, если AB не равен C, то есть короткий сертификат, который работает: запись C, которая является неправильной, и соответствующая строка A и столбец B.
Робин Котари

Ответы:

14

Вот быстрый аргумент, почему он работает над кольцами. Для заданных матриц , B , C мы проверяем A B = C , выбирая случайный битовый вектор v , а затем проверяя, если A B v = C v . Это явно проходит , если A B = C .ABCAB=CvABv=CvAB=C

Предположим, что и A B v = C v . Пусть D = A B - C . D ненулевая матрица, для которой D v = 0 . Какова вероятность того, что это произойдет? Пусть D [ i , j ] ненулевая запись. По предположению, j D [ i , j ] v [ j ] = 0ABCABv=CvD=ABCDDv=0D[i,j]jD[i,j]v[j]=0, С вероятностью , об [ J ' ] = 1 , так что мы имеем1/2v[j]=1

.D[i,j]+jjD[i,j]v[j]=0

Любое кольцо при его операции сложения является аддитивной группой, поэтому существует единственное обратное к , т. Е. - D [ i , j ] . Теперь вероятность плохого события - D [ я ' , J ' ] = Σ J J ' D [ я ' , J ] v [ J ] не более 1 / 2D[i,j]D[i,j]D[i,j]=jjD[i,j]v[j]1/2, (Одним из способов убедиться в этом является «принцип отсроченных решений»: для того, чтобы сумма была равна , по крайней мере еще один D [ i , j ] должен быть ненулевым. Поэтому рассмотрим v [ j ] соответствует этим другим ненулевым элементам. Даже если мы установим все эти v [ j ] за исключением одного из них оптимальным образом , вероятность того, что последний из них равен 0 или 1, остается равной.D[i,j]D[i,j]v[j]v[j]01, Но до сих пор только один из этих значений может внести окончательную сумму , равную .) Таким образом , с вероятностью по крайней мере 1 / 4 , мы успешно находим , что D V 0 , когда D равно нулю. (Примечание: v [ j ] и v [ j ] независимо выбраны для j j .)D[i,j]1/4Dv0Dv[j]v[j]jj

Как видите, приведенный выше аргумент зависит от вычитания. Так что он не будет работать (например) на произвольных коммутативных полуколец. Возможно, вы могли бы ослабить мультипликативные свойства алгебраической структуры и все же получить результат?

Райан Уильямс
источник
Здорово спасибо Я вижу вашу точку зрения о возможности уменьшения ограничений на мультипликативную структуру. Просто для моей информации, разве это не тот же алгоритм, что и в оригинальной статье Фрейвальдса?
Робин Котари
Алгоритм Фрейвалдса выбирает случайный вектор с компонентами в {-1,1}. Это тоже работает. Если вы более осторожны , вы можете получить вероятность успеха, по крайней мере . 1/2
Райан Уильямс