¿Cuál es la estructura más general sobre la cual se puede hacer la verificación del producto matricial en el tiempo

18

En 1979, Freivalds demostró que la verificación de los productos matriciales en cualquier campo se puede hacer en un tiempo aleatorizado de . Más formalmente, dadas tres matrices A, B y C, con entradas de un campo F, el problema de verificar si AB = C tiene un algoritmo de tiempo O ( n 2 ) aleatorio .O(n2)O(n2)

Esto es interesante porque el algoritmo más rápido conocido para multiplicar matrices es más lento que esto, por lo que verificar si AB = C es más rápido que calcular C.

Quiero saber cuál es la estructura algebraica más general sobre la cual la verificación de productos de matriz todavía tiene un algoritmo de tiempo (aleatorio). Dado que el algoritmo original funciona en todos los campos, creo que también funciona en todos los dominios integrales.O(n2)

La mejor respuesta que pude encontrar a esta pregunta fue en Equivalencias subcúbicas entre problemas de trayectoria, matriz y triángulo , donde dicen que "la verificación del producto matricial sobre los anillos se puede hacer en tiempo aleatorio [BK95]". ([BK95]: M. Blum y S. Kannan. Diseño de programas que verifican su trabajo. J. ACM, 42 (1): 269–291, 1995.)O(n2)

Primero, ¿son los anillos la estructura más general sobre la cual este problema tiene un algoritmo aleatorio ? En segundo lugar, no pude ver cómo los resultados de [BK95] muestran un algoritmo de tiempo O ( n 2 ) en todos los anillos. ¿Alguien puede explicar cómo funciona?O(n2)O(n2)

Robin Kothari
fuente
Una pregunta estúpida: ¿es obvio que la verificación determinista es tan difícil como la multiplicación? ¿Qué pasa si le dan no solo A, B y C sino también un certificado compacto? ¿Ayuda algo?
Jukka Suomela
@ Jukka: Creo que el mejor algoritmo determinista para este problema no es más rápido que la multiplicación de matrices, pero no sé si hay una razón por la cual este debería ser el caso. Acerca de la segunda pregunta, si AB no es igual a C, entonces hay un certificado corto que funciona: la entrada de C que es incorrecta y la fila correspondiente de A y la columna de B.
Robin Kothari

Respuestas:

14

Aquí hay un argumento rápido de por qué funciona sobre anillos. Dadas las matrices , B , C , verificamos A B = C seleccionando un vector de bits aleatorio v , luego verificando si A B v = C v . Esto pasa claramente si A B = C .ABCAB=CvABv=CvAB=C

Suponga que y A B v = C v . Deje D = A B - C . D es una matriz distinta de cero para la cual D v = 0 . ¿Cuál es la probabilidad de que esto ocurra? Sea D [ i , j ] una entrada distinta de cero. Por supuesto, j D [ i , j ] v [ j ] = 0ABCABv=CvD=ABCDDv=0D[i,j]jD[i,j]v[j]=0. Con probabilidad , v [ j ' ] = 1 , por lo que tenemos1/2v[j]=1

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

Cualquier anillo bajo su operación de suma es un grupo aditivo, por lo que hay un inverso único de , es decir, - D [ i , j ] . Ahora, la probabilidad de que el evento malo - D [ i ' , j ' ] = Σ j j ' D [ i ' , j ] v [ j ] es como máximo de 1 / 2D[i,j]D[i,j]D[i,j]=jjD[i,j]v[j]1/2. (Una forma de ver esto es el "principio de decisiones diferidas": para que la suma sea igual a , al menos otra D [ i , j ] debe ser distinta de cero. v [ j ] corresponde a estas otras entradas distintas de cero. Incluso si establecemos todas estas v [ j ] a excepción de una de ellas de manera óptima , todavía existe la misma probabilidad de que la última sea 0 o 1D[i,j]D[i,j]v[j]v[j]01, Pero sólo uno de estos valores podrían hacer que la suma final igual a .) Así que con una probabilidad de al menos 1 / 4 , encontramos que el éxito D V 0 , cuando D es distinto de cero. (Nota v [ j ] y v [ j ] se eligen independientemente para j j .)D[i,j]1/4Dv0Dv[j]v[j]jj

Como puede ver, el argumento anterior depende de la resta. Por lo tanto, no funcionará (por ejemplo) en semirreferencias conmutativas arbitrarias. ¿Quizás podría relajar las propiedades multiplicativas de la estructura algebraica y aún así obtener el resultado?

Ryan Williams
fuente
Genial gracias. Veo su punto sobre la posibilidad de reducir las restricciones en la estructura multiplicativa. Solo para mi información, ¿no es este el mismo algoritmo que el del artículo original de Freivalds?
Robin Kothari
El algoritmo de Freivalds elige un vector aleatorio con componentes en {-1,1}. Eso tambien funciona. Si usted es más cuidadoso puede obtener la probabilidad de éxito sea al menos . 1/2
Ryan Williams