¿Ejemplos del precio de la abstracción?

La informática teórica ha proporcionado algunos ejemplos del "precio de la abstracción". Los dos más destacados son para la eliminación y clasificación gaussianas. A saber:

• Se sabe que la eliminación gaussiana es óptima para, por ejemplo, calcular el determinante si restringe las operaciones a filas y columnas como un todo [1]. Obviamente, el algoritmo de Strassen no obedece esa restricción, y es asintóticamente mejor que la eliminación gaussiana.
• En la ordenación, si trata los elementos de la lista como cuadros negros que solo se pueden comparar y mover, entonces tenemos el límite inferior estándar teórico de la información. Sin embargo, los árboles de fusión superan este límite, por lo que yo entiendo, el uso inteligente de la multiplicación.$n \log n$

¿Hay otros ejemplos del precio de la abstracción?

Para ser un poco más formal, estoy buscando ejemplos en los que se conozca incondicionalmente un límite inferior en algún modelo débil de cómputo, pero se sabe que se viola en un modelo más fuerte. Además, la debilidad del modelo débil debería presentarse en forma de una abstracción , que es una noción subjetiva. Por ejemplo, no considero que la restricción a los circuitos monótonos sea una abstracción. Esperemos que los dos ejemplos anteriores aclaren lo que estoy buscando.

[1] KLYUYEV, VV y NI KOKOVKIN-SHcHERBAK: Sobre la minimización del número de operaciones aritméticas para la solución de sistemas de ecuaciones algebraicas lineales. Traducción por GI TEE: Informe técnico CS 24, junio t4, t965, Departamento de Informática, Universidad de Stanford.

Otro hermoso ejemplo del precio de la abstracción: la codificación de red . Se sabe que en la configuración de multidifusión, la relación max-flow-min-cut no es de igualdad (lo primario y lo dual no coinciden). Sin embargo, los modelos tradicionales suponen un flujo que simplemente se pasa y no se "procesa" de ninguna manera. Con la codificación de red, puede superar este límite combinando inteligentemente los flujos. Este ejemplo fue un gran motivador para el estudio de la codificación de red en primer lugar.

La programación puramente funcional es una abstracción popular que ofrece, al menos según sus defensores, un gran aumento en el poder expresivo del código, entre otros beneficios. Sin embargo, dado que es un modelo restrictivo de la máquina, en particular, que no permite memoria mutable, plantea la cuestión de la desaceleración asintótica en comparación con el modelo habitual (RAM).

Hay un gran hilo sobre esta pregunta aquí . Las principales conclusiones parecen ser:

1. Puede simular memoria mutable con un árbol binario equilibrado, por lo que la desaceleración del peor de los casos es O (log n).
2. Con una evaluación entusiasta , hay problemas por los cuales esto es lo mejor que puede hacer.
3. Con la evaluación diferida , no se sabe si existe o no una brecha. Sin embargo, hay muchos problemas naturales para los cuales ningún algoritmo puramente funcional conocido coincide con la complejidad óptima de RAM.

Me parece que esta es una pregunta sorprendentemente básica para ser abierta.

Si bien su pregunta se centra en la teoría de la complejidad, cosas similares pueden suceder en otros campos, como la teoría de los lenguajes de programación. Aquí hay un par de ejemplos en los que la abstracción hace que algo sea indecidible (es decir, el límite inferior en el modelo débil es imposible, mientras que el modelo fuerte permite que se exprese el algoritmo):

• En el cálculo lambda, hay funciones que no puede expresar directamente (es decir, como un término lambda que beta-reduce al resultado deseado). Un ejemplo es paralelo o (una función de dos argumentos que devuelve el que termina). Otro ejemplo es una función que imprime su argumento literalmente (una función obviamente no puede distinguir entre dos argumentos equivalentes beta). La falta de expresividad se debe a la imposición de la abstracción de que los términos lambda equivalentes beta deben tratarse de manera idéntica.

• En un lenguaje de tipo estático que solo tiene polimorfismo paramétrico , como ML sin extensión elegante, es imposible escribir algunas funciones: obtienes teoremas de forma gratuita . Por ejemplo, una función cuyo tipo es (cualquiera que sea el tipo del argumento, devolver un objeto del mismo tipo) debe ser la función de identidad o no terminar. La falta de expresividad se debe a la abstracción de que si no conoce el tipo de valor, es opaco (solo puede pasarlo).$\forall\alpha, \alpha\to\alpha$

El "precio de la abstracción" también se puede encontrar al resolver el problema de logaritmo discreto en criptografía. Shoup (1997) ha demostrado que cualquier enfoque genérico (es decir, algoritmos que usan solo operaciones de grupo) tiene que usar al menos operaciones de grupo , donde es el tamaño del grupo. Esto coincide con la complejidad del ataque genérico de cumpleaños . Sin embargo, algoritmos como el cálculo del Índice o el algoritmo de Pohlig-Hellman se basan en la estructura teórica numérica de para obtener algoritmos ligeramente más rápidos (al menos en grupos de orden uniforme).m Z ∗ $\Omega(\sqrt{m})$$m$$\mathbb{Z}_n^*$

Esta observación es una de las razones de la popularidad de la criptografía de curva elíptica (a diferencia de la criptografía en grupos como ) ya que, esencialmente, solo conocemos enfoques genéricos para resolver el problema de logaritmo discreto en grupos basados ​​en elíptica curvas.$\mathbb{Z}_n^*$

Aquí hay un ejemplo de algoritmos gráficos. Dado un grafo dirigido con pesos no negativos en los bordes, los todos los pares de cuello de botella caminos problema consiste en calcular, para todos los pares de vértices y , el flujo máximo que puede ser empujado a lo largo algún camino de a . (Formalmente, solo estamos maximizando el peso mínimo de un borde en cualquier ruta de a . Más formalmente, estamos reemplazando y en la definición de las rutas más cortas de todos los pares con y .)$s$$t$$s$$t$$s$$t$$\min$$+$$\max$$\min$

Sea el número de vértices en el gráfico de entrada. Se sabía que este problema requería tiempo en el modelo de comparación de rutas de Karger, Koller y Phillips , al igual que el problema de las rutas más cortas de todos los pares. (El modelo de trayectoria de comparación de soporta los algoritmos tradicionales, como Floyd-Warshall.) Sin embargo, a diferencia de todos o por pares caminos más cortos, resulta que todos los pares de cuello de botella caminos pueden ser resueltos en menos de de tiempo usando Multiplicación rápida de matrices.$n$$\Omega(n^3)$$O(n^{2.8})$

Según una discusión en esta pregunta , muchos problemas en la geometría computacional tienen límites inferiores en el árbol de decisión algebraico o en los modelos de cálculo de árbol de computación algebraico, derivados de problemas fundamentales como la clasificación o la distinción de elementos . No es difícil encontrar documentos que afirmen que los límites superiores de en problemas relacionados, como la construcción de triangulaciones de Delaunay, son óptimos, ya que coinciden con estos límites inferiores.$\Omega(n\log n)$$O(n\log n)$

Pero cuando la entrada se especifica en coordenadas cartesianas enteras (como es frecuente en la práctica, el punto flotante es un mal ajuste para la geometría computacional), estos límites inferiores no coinciden con el modelo computacional. Quizás no sea sorprendente que los problemas de tipo de búsqueda de rango ortogonal se puedan resolver más rápido utilizando técnicas adaptadas de la clasificación de enteros, pero incluso los problemas no ortogonales a menudo pueden tener algoritmos más rápidos (que resuelven el problema exactamente, en modelos de cálculo que permiten la aritmética de enteros con O (1) ) veces la precisión de los enteros de entrada). Ver, por ejemplo, arXiv: 1010.1948 para un conjunto de ejemplos.

Hay muchos ejemplos de este tipo en criptografía, especialmente pruebas de conocimiento cero. Ver, por ejemplo, la tesis:

Boaz Barak, Técnicas sin caja negra en criptografía, 2003.

(Por cierto, el título de la tesis proporciona una prueba de conocimiento cero de la validez de este comentario :)

Los árboles de decisión algebraicos se utilizan como base en la geometría computacional para mostrar que muchos problemas simples como Element Uniqueness son . Estos límites inferiores se utilizan para mostrar problemas más complicados, como los diagramas de Voronoi que también tienen límites inferiores . Más tarde me sorprendió leer un algoritmo de tiempo esperado para resolver el par de puntos más cercano en el plano, que es una generalización de la unicidad del elemento. Se escapa del árbol de decisión algebraico vinculado mediante el hash. Lo encontré en el libro Algorithm Design de Klein y Tardos. Hay un algoritmo similar pero más complicado para resolver el mismo problema descrito en el blog de RJ Lipton .$\Omega(n \log n)$$\Omega(n \log n)$$O(n)$

Referencia:

• Richard J. Lipton, " Rabin lanza una moneda ", marzo de 2009
  publicado en la carta Perdida de Godel y el blog P = NP .

Considere algoritmos distribuidos deterministas sincrónicos para reducir el número de colores en un gráfico de ciclo de a . Es decir, se le da una coloración adecuada del ciclo y le gustaría generar una coloración adecuada del ciclo; Cada nodo del ciclo es un procesador.$k$$3$$k$$3$

Si asume un modelo basado en la comparación (trata los colores como cuadros negros que solo pueden transmitirse de un nodo a otro y compararse entre sí), obtiene un límite inferior trivial de para el número de rondas de comunicación$k$$\Omega(k)$

Sin embargo, podría decirse que esta abstracción es claramente errónea: si puede transmitir algo en una red de comunicación, tendrá alguna forma de codificar "algo" como una cadena de bits. Y ahora las cosas empiezan a verse mucho mejor.

Si sus colores no son cuadros negros sino enteros , entonces puede hacer la reducción de color utilizando técnicas de Cole-Vishkin en rondas de comunicación . Incluso si sus colores son cadenas de bits enormes , como enteros de , obtendrá el mismo límite .$1, 2, ..., k$$O(\log^* k)$$1, 2, ..., 10^{10^k}$$O(\log^* k)$

En pocas palabras: el precio de la abstracción "incorrecta": vs. .$O(\log^* k)$$\Omega(k)$

Un ejemplo que me viene a la mente es el cálculo del volumen. Un resultado de Barany y Furedi es que necesita un número exponencial de consultas y hay un algoritmo de tiempo polinómico aleatorio de Dyer-Frieze-Kannan . La brecha representa el premio de la abstracción y también el beneficio de la aleatoriedad, pero creo que la razón principal de la brecha es el precio de la abstracción. (Espero haber entendido la pregunta y va en la dirección correcta).

Esto probablemente no sea exactamente lo que tenía en mente. Pero en cierto sentido, la independencia de P vs NP de los oráculos es un buen ejemplo. Lo que realmente dice es que si lo único que le importa es la simulación y la enumeración (es decir, si ese es su "modelo" de cálculo), entonces no puede separar estas clases o colapsarlas.

Un ejemplo algorítmico más concreto proviene de la búsqueda de rango aproximado en la dirección "inversa". Específicamente, la mayoría de los problemas de búsqueda de rango se expresan como sumas de semigrupo, y los límites inferior / superior se expresan sin tener en cuenta la estructura de este semigrupo (a excepción de algunas condiciones técnicas leves). Un trabajo reciente de Arya, Malamatos y Mount muestra que si observa de cerca la estructura del semigrupo (las propiedades de idempotencia e integralidad), puede probar límites diferentes (y más estrictos) para la búsqueda de rango aproximado.

El teorema de muestreo de Shannon-Nyquist propone una condición suficiente para los límites teóricos de la información sobre la comunicación. La teoría de muestreo se trabaja en torno a ejemplos en los que la señal entrante tiene una representación compacta / aleatoria. Los avances recientes en el muestreo muestran que esta abstracción tal vez tenga un precio: que el tipo de cosas que nos interesa medir generalmente tiene representaciones dispersas, por lo que estos límites no son ajustados. Además, la información se puede codificar de una manera mucho más densa de lo que se pensaba originalmente.

• Los códigos de corrección de errores sugieren que alguna reevaluación del límite de Shannon en paisajes de redes sujetos a ruido.
• El nuevo campo de detección de compresión empuja la reconstrucción de las variedades de imágenes que encontramos interesantes más allá del límite de Shannon.

Muchos problemas interesantes que surgen con las ciencias de la naturaleza resultan ser NP-hard en el sentido clásico. Si bien esta noción es teóricamente perfectamente válida, no ayuda al biólogo o al físico de ninguna manera. Encontramos que algunos problemas NP-hard son parámetros fijos tratables y, a menudo, con un parámetro que se observa limitado por una pequeña constante en el mundo real.

Es decir, TCS nos dice que no esperamos una solución eficiente para el problema abstracto, pero que podemos resolver las instancias realmente rápidas, un gran vacío.

En este artículo http://www.mimuw.edu.pl/~szymtor/papers/atom-turing.pdf estudiamos las máquinas de Turing que tienen acceso limitado a los datos. Esto se formaliza como invariante bajo automorfismos de una estructura relacional; por ejemplo, en el límite inferior O (n log n) para la clasificación, se podría decir que la máquina puede procesar y almacenar números racionales, pero sus transiciones deben ser invariables bajo automorfismos de (Q, <), es decir, biyecciones monótonas. La definición formal es más complicada, para especificar con precisión qué tipo de estructuras de datos puede almacenar la máquina en su memoria (debería ser "finita"
en algún sentido, pero permitimos almacenar estructuras más complicadas que solo tuplas de valores de datos, como tuplas desordenadas).

En el documento probamos algunos límites inferiores para otras máquinas de Turing con "acceso restringido a datos". En particular, mostramos que:

• Una máquina de Turing determinista que puede manejar vectores (por ejemplo, sobre el campo de dos elementos), pero solo puede usar pruebas de suma e igualdad de vectores, no puede determinar en un tiempo polinómico si una lista dada de vectores es linealmente dependiente (formalmente, las transiciones de las máquinas deberían ser invariante bajo automorfismos del espacio vectorial). Esto se opone a las máquinas no deterministas, que simplemente pueden adivinar una combinación de los vectores que se suman a 0. Observe que la eliminación gaussiana se ejecuta en tiempo polinómico, pero tiene acceso a las coordenadas de los vectores; en particular, sus transiciones no son invariantes bajo los automorfismos del espacio vectorial.

• En un modelo adecuadamente definido, las máquinas de Turing que pueden comparar números naturales solo con respecto a la igualdad (ni siquiera <) no pueden determinarse. Aquí, consideramos la estructura relacional (N, =) y las máquinas que son invariables bajo sus automorfismos. Hay una construcción (similar a la construcción Cai-Furer-Immerman de la teoría del modelo finito) que muestra que, de hecho, en este modelo P ≠ NP. Permitir que las máquinas comparen los números usando <les da suficiente poder para determinar.

Un precio general de abstracción está presente en los marcos de caja negra como la complejidad del árbol de decisión o la complejidad de la consulta cuántica. Si restringimos el análisis a estos modelos, a menudo podemos encontrar muy buenos límites en la complejidad de las tareas. De hecho, para la consulta cuántica básicamente podemos resolver la complejidad de los problemas porque el método negativo del adversario proporciona límites inferiores ajustados (dentro de un factor de log n / loglog n: 1005.1601 ). Esto nos brinda una gran herramienta para analizar la complejidad de la consulta, pero a menudo se hace difícil comparar la complejidad de la consulta con una complejidad de tiempo / espacio de máquina de turing más estándar (excepto como un límite inferior bruto).

Aquí hay dos ejemplos, ambos relacionados con modelos continuos versus modelos discretos:

1. Supongamos que hay un tesoro (infinitamente pequeño) escondido en el intervalo , en la posición . Queremos encontrar el tesoro cavando. Cada vez que excavamos en la posición , recibimos retroalimentación de si , o . Obviamente, si puede ser cualquier número real, entonces cualquier algoritmo de búsqueda nunca terminará. puede ser muy pequeño, pero es posible que nunca lleguemos a . x y x < y x = y x > y x | x - y | y = $[0,1]$$x$$y$$x<y$$x=y$$x>y$$x$$|x-y|$$y=x$

   Sin embargo, podemos ampliar el modelo de búsqueda para permitir el barrido continuo. En este modelo, simplemente dejamos que ejecute continuamente durante el intervalo , y recibimos comentarios cada vez que .[ 0 , 1 ] y = $y$$[0,1]$$y=x$

2. La motivación para el problema A proviene del problema de la división de pasteles sin envidia . Stromquist demostró que ningún protocolo finito (incluso si no está limitado) puede garantizar una división libre de envidia de un pastel entre tres o más jugadores, si cada jugador va a recibir una sola pieza conectada.

   Sin embargo, como explicaron Aumann y Dombb más adelante , este resultado se aplica solo a un modelo de corte discreto, donde "En cada paso, el protocolo selecciona un jugador y un número real , e invita al jugador a hacer una marca en el punto único para el cual "," y no para casos donde, por ejemplo, algún mediador tiene información completa de las funciones de valoración de los jugadores y propone una división basada en esta información ". α i x v i ( 0 , x ) = $i$$\alpha$$i$$x$$vi(0,x) = \alpha$

   Además, el resultado no se relaciona con algoritmos con operaciones continuas, como los procedimientos de cuchilla móvil.

Cuando se expresa en lógica de primer orden, cualquier prueba del principio de casillero para n fijo es exponencial en longitud. Sin embargo, con la aritmética, la prueba se puede expresar de manera mucho más concisa.

El éxito de los solucionadores SMT provino de retroceder del modelo abstracto de reducción de problemas a SAT, lo que permite que las teorías más ricas reduzcan en gran medida la cantidad de cálculos necesarios.