En informática , un algoritmo de prueba de propiedades para un problema de decisión es un algoritmo cuya complejidad de consulta a su entrada es mucho menor que el tamaño de la instancia del problema. Por lo general, los algoritmos de prueba de propiedades se utilizan para decidir si algún objeto matemático (como un gráfico o una función booleana ) tiene una propiedad "global" o está "lejos" de tener esta propiedad, utilizando solo una pequeña cantidad de consultas "locales" para el objeto.
Por ejemplo, el siguiente problema de promesa admite un algoritmo cuya complejidad de consulta es independiente del tamaño de la instancia (para una constante arbitraria ε> 0):
- "Dado un gráfico G en n vértices, decida si G es bipartito o G no puede hacerse bipartito incluso después de eliminar un subconjunto arbitrario de como máximo bordes de G ".
Los algoritmos de prueba de propiedad son fundamentales para la definición de pruebas probabilísticamente verificables , ya que una prueba probabilísticamente verificable es esencialmente una prueba que puede verificarse mediante un algoritmo de prueba de propiedad.
Definición y variantes
Formalmente, un algoritmo de prueba de propiedad con complejidad de consulta q ( n ) y parámetro de proximidad ε para un problema de decisión L es un algoritmo aleatorio que, en la entrada x (una instancia de L ) realiza como máximo q (| x |) consultas ax y se comporta de la siguiente manera:
- Si x está en L , el algoritmo acepta x con probabilidad de al menos ⅔.
- Si x está ε-lejos de L , el algoritmo rechaza x con una probabilidad de al menos ⅔.
Aquí, " x está ε-lejos de L " significa que la distancia de Hamming entre x y cualquier cuerda en L es al menos ε | x |.
Se dice que un algoritmo de prueba de propiedad tiene un error unilateral si satisface la condición más fuerte de que la probabilidad de aceptación para las instancias x ∈ L es 1 en lugar de ⅔.
Se dice que un algoritmo de prueba de propiedades no es adaptable si realiza todas sus consultas antes de "observar" las respuestas a consultas anteriores. Se puede considerar que un algoritmo de este tipo funciona de la siguiente manera. Primero, el algoritmo recibe su entrada. Antes de mirar la entrada, utilizando su aleatoriedad interna, el algoritmo decide qué símbolos de la entrada se van a consultar. A continuación, el algoritmo observa estos símbolos. Finalmente, sin realizar consultas adicionales (pero posiblemente usando su aleatoriedad), el algoritmo decide si acepta o rechaza la entrada.
Características y limitaciones
El principal parámetro de eficiencia de un algoritmo de prueba de propiedades es su complejidad de consulta, que es el número máximo de símbolos de entrada inspeccionados en todas las entradas de una longitud determinada (y todas las elecciones aleatorias realizadas por el algoritmo). A uno le interesa diseñar algoritmos cuya complejidad de consulta sea lo más pequeña posible. En muchos casos, el tiempo de ejecución de los algoritmos de prueba de propiedades es sublineal en la longitud de la instancia. Normalmente, el objetivo es primero hacer que la complejidad de la consulta sea lo más pequeña posible en función del tamaño de la instancia n , y luego estudiar la dependencia del parámetro de proximidad ε.
A diferencia de otras configuraciones teóricas de la complejidad, la complejidad de la consulta asintótica de los algoritmos de prueba de propiedades se ve afectada dramáticamente por la representación de instancias. Por ejemplo, cuando ε = 0.01, el problema de probar la bipartita de los gráficos densos (que están representados por su matriz de adyacencia ) admite un algoritmo de complejidad de consulta constante. Por el contrario, los gráficos dispersos en n vértices (que están representados por su lista de adyacencia) requieren algoritmos de prueba de propiedades de complejidad de consulta.
La complejidad de la consulta de los algoritmos de prueba de propiedades crece a medida que el parámetro de proximidad ε se vuelve más pequeño para todas las propiedades no triviales. Esta dependencia de ε es necesaria ya que un cambio de menos de ε símbolos en la entrada no puede detectarse con probabilidad constante utilizando menos de O (1 / ε) consultas. Se pueden probar muchas propiedades interesantes de los gráficos densos utilizando la complejidad de la consulta que depende solo de ε y no del tamaño del gráfico n . Sin embargo, la complejidad de la consulta puede crecer enormemente en función de ε. Por ejemplo, durante mucho tiempo, el algoritmo más conocido para probar si un gráfico no contiene ningún triángulo tenía una complejidad de consulta que es una función de torre de poli (1 / ε), y solo en 2010 se ha mejorado a una función de torre. de log (1 / ε). Una de las razones de este enorme crecimiento en los límites es que muchos de los resultados positivos de las pruebas de propiedad de los gráficos se establecen utilizando el lema de regularidad de Szemerédi , que también tiene límites de tipo torre en sus conclusiones. La conexión de las pruebas de propiedad con el lema de regularidad de Szemerédi y los lemas de eliminación de gráficos relacionados se detalla a continuación.
Prueba de propiedad de gráficos
Para gráficos con n vértices, la noción de distancia que usaremos es la distancia de edición. Es decir, decimos que la distancia entre dos gráficas es la menor ε tal que se puede sumar y / o eliminarbordes y pasar del primer gráfico al segundo. Bajo una representación razonable de gráficos, esto es equivalente a la definición anterior de distancia de Hamming (hasta posiblemente un cambio de constantes). Para los gráficos, hay una caracterización de qué propiedades son fáciles de probar. Es decir, las propiedades que son fáciles de probar son precisamente aquellas propiedades que son (casi) hereditarias. Estas declaraciones se aclararán a continuación. En primer lugar, cuando una propiedad es fácil de probar, queremos decir que tiene un probador ajeno.
Probadores ajenos
De manera informal, un probador ajeno a una propiedad de gráfico P es un algoritmo que toma como entrada un parámetro ε y un gráfico G , y luego se ejecuta como un algoritmo de prueba de propiedad en G para la propiedad P con parámetro de proximidad ε que hace exactamente q (ε) consultas a G . Fundamentalmente, el número de consultas que hace un evaluador ajeno es una constante que solo depende de ε. La definición formal es que un probador ajeno es un algoritmo que toma como entrada un parámetro ε. Calcula un número entero q (ε) y luego le pide a un oráculo un subgrafo inducido H en exactamente q (ε) vértices de G elegidos uniformemente al azar. A continuación, acepta o rechaza según ε y H . Como antes, se dice que las pruebas para la propiedad P si acepta con probabilidad al menos ⅔ para G que tiene la propiedad P , y rechaza con probabilidad al menos ⅔ o G que es ε-lejos de tener la propiedad P . En completa analogía con los algoritmos de prueba de propiedades, podemos hablar de probadores inconscientes con error unilateral.
Prueba de propiedades hereditarias
Una propiedad hereditaria es una propiedad que se conserva al eliminar los vértices. Algunas propiedades hereditarias importantes son la ausencia de H (para algunos gráficos H ), k -colorabilidad y planaridad . Todas las propiedades hereditarias son comprobables, y hay una prueba de este hecho utilizando una versión del lema de eliminación de grafos para familias infinitas de subgrafos inducidos. De hecho, una inversa aproximada de esto también es cierta: las propiedades que tienen probadores inconscientes con error unilateral son casi hereditarias (Alon y Shapira 2008), en un sentido que no se precisará aquí.
Ejemplo: probar la ausencia de triángulos
En esta sección, esbozaremos una prueba de la existencia de un probador ajeno a la ausencia de triángulos; esta prueba es una aplicación del lema de eliminación de triángulos .
Bosquejo de la prueba: si una gráfica G está ε-lejos de estar libre de triángulos, entonces, según el lema de eliminación de triángulos, hay una constante (computable)para que G tenga al menostriangulos. Las muestras del probador inconscientetriples de vértices independientemente al azar del gráfico. Acepta si ningún triple de vértices induce un triángulo, y rechaza en caso contrario.
- Si G está libre de triángulos, entonces claramente este algoritmo siempre acepta.
- Si G está ε-lejos de estar libre de triángulos, entonces más defracción de los triples de vértices en G induce un triángulo, y entonces no es difícil ver que existe una probabilidad mayor que ⅔ de que el algoritmo encuentre al menos un triángulo.
Por lo tanto, el algoritmo anterior es un probador inconsciente con un error unilateral de ausencia de triángulos.
Referencias
- Goldreich, Oded (2017). Introducción a las pruebas de propiedad . Prensa de la Universidad de Cambridge. ISBN 9781107194052.
- Ron, Dana (2000). Ensayos de propiedad (informe técnico).
- Rubinfeld, Ronitt; Shapira, Asaf (2011). "Algoritmos de tiempo sublineal". Revista SIAM de Matemática Discreta . 25 (4): 1562-1588. CiteSeerX 10.1.1.221.1797 . doi : 10.1137 / 100791075 .
- Goldreich, Oded (1999). "Prueba de propiedad combinatoria (una encuesta)" . Métodos de aleatorización en el diseño de algoritmos . 43 : 45–59. ISBN 0821870874.
- Fox, Jacob (2010). "Una nueva prueba del lema de eliminación de gráficos". arXiv : 1006.1300 .
- Alon, Noga ; Shapira, Asaf (2008). "Una caracterización de las propiedades del gráfico (natural) comprobables con error unilateral" (PDF) . Revista SIAM de Computación . 37 : 1703-1727.