El problema de Pagh

Algoritmo para la intersección de conjuntos

El problema de Pagh es un problema de estructura de datos que se utiliza a menudo ^[1]^[2] al estudiar los límites inferiores en informática y que lleva el nombre de Rasmus Pagh . Mihai Pătrașcu fue el primero en dar límites inferiores para el problema. ^[3] En 2021 se demostró que, dadas las conjeturas populares, el algoritmo de tiempo lineal ingenuo es óptimo. ^[4]

Definición

Se nos dan como entradas subconjuntos sobre un universo . ${\estilo de visualización k}$ $X_{1},X_{2},\puntos ,X_{k}$ $U=\{1,\puntos,k\}$

Debemos aceptar actualizaciones del siguiente tipo: Dado un puntero a dos subconjuntos y , crear un nuevo subconjunto . $Estilo de visualización X_{1}$ $Estilo de visualización X_{2}$ $Estilo de visualización X_{1}\cap X_{2}}$

Después de cada actualización, debemos indicar si el nuevo subconjunto está vacío o no.

Referencias

^ Abboud, Amir y Virginia Vassilevska Williams. "Las conjeturas populares implican límites inferiores sólidos para problemas dinámicos". 55.° Simposio anual sobre fundamentos de la informática del IEEE de 2014. IEEE, 2014.
^ Chen, Lijie, et al. "Separación casi óptima entre estructuras de datos parcial y totalmente retroactivas". 16.º Simposio y talleres escandinavos sobre teoría de algoritmos. 2018.
^ Patrascu, Mihai. "Hacia límites inferiores polinómicos para problemas dinámicos". Actas del cuadragésimo segundo simposio de la ACM sobre teoría de la computación. 2010.
^ Henzinger, Monika, et al. "Unificación y fortalecimiento de la dureza para problemas dinámicos a través de la conjetura de multiplicación de matriz-vector en línea". Actas del cuadragésimo séptimo simposio anual de la ACM sobre teoría de la computación. 2015.

[1] Abboud, Amir y Virginia Vassilevska Williams. "Las conjeturas populares implican límites inferiores sólidos para problemas dinámicos". 55.° Simposio anual sobre fundamentos de la informática del IEEE de 2014. IEEE, 2014.

[2] Chen, Lijie, et al. "Separación casi óptima entre estructuras de datos parcial y totalmente retroactivas". 16.º Simposio y talleres escandinavos sobre teoría de algoritmos. 2018.

[3] Patrascu, Mihai. "Hacia límites inferiores polinómicos para problemas dinámicos". Actas del cuadragésimo segundo simposio de la ACM sobre teoría de la computación. 2010.

[4] Henzinger, Monika, et al. "Unificación y fortalecimiento de la dureza para problemas dinámicos a través de la conjetura de multiplicación de matriz-vector en línea". Actas del cuadragésimo séptimo simposio anual de la ACM sobre teoría de la computación. 2015.