Hipótesis de expansión de conjuntos pequeños

Supuesto de dureza computacional

La hipótesis de la expansión de conjuntos pequeños o la conjetura de la expansión de conjuntos pequeños en la teoría de la complejidad computacional es una suposición de dureza computacional no probada . Según la hipótesis de expansión de conjuntos pequeños, se supone que es computacionalmente inviable distinguir entre una determinada clase de gráficos de expansión llamados "expansores de conjuntos pequeños" y otros gráficos que están muy lejos de ser expansores de conjuntos pequeños. Esta suposición implica la dureza de varios otros problemas computacionales y la optimización de ciertos algoritmos de aproximación conocidos .

La hipótesis de la expansión de conjuntos pequeños está relacionada con la conjetura de los juegos únicos , otro supuesto de dureza computacional no probado según el cual aproximar con precisión el valor de ciertos juegos es computacionalmente inviable. Si la hipótesis de la expansión de conjuntos pequeños es cierta, también lo es la conjetura de los juegos únicos.

Fondo

Expansión de borde versus conjunto pequeño. El gráfico de hipercubo de 16 vértices que se muestra tiene ocho aristas rojas y ocho vértices azules que se muestran a la izquierda, por lo que su expansión de aristas es 1. Para conjuntos pequeños de como máximo vértices, la relación mínima entre aristas y vértices es , para los ocho bordes rojos y cuatro vértices azules a la derecha, por lo que su pequeña expansión del conjunto es 2. ${\displaystyle |\partial X|/|X|=8/8=1}$ ${\displaystyle n/\log _{2}n=4}$ ${\displaystyle 8/4=2}$

La expansión de aristas de un conjunto de vértices en un gráfico se define como donde las barras verticales denotan el número de elementos de un conjunto y denota el conjunto de aristas que tienen un punto final y el otro punto final en su complemento. ^[a] Este número puede ser tan bajo como cero, cuando es un componente conectado del gráfico, porque en este caso no hay bordes que se conecten con otras partes del gráfico. Una gráfica se llama regular o regular cuando cada vértice incide en el mismo número de aristas, el grado de la gráfica. Para un gráfico regular, la máxima expansión de borde posible es . Esta expansión se logra mediante cualquier subconjunto que induzca un conjunto independiente , como en este caso pertenecen todas las aristas que tocan los vértices . ^{[1] [2]} ${\displaystyle X}$ ${\displaystyle G}$ $${\displaystyle {\frac {|\partial X|}{|X|}},}$$ ${\displaystyle \partial X}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle d}$ ${\displaystyle d}$ ${\displaystyle d}$ ${\displaystyle d}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle \partial X}$

La expansión de aristas de un gráfico con vértices se define como la expansión de aristas mínima entre sus subconjuntos de como máximo vértices. ^[b] En cambio, la expansión del conjunto pequeño se define como el mismo mínimo, pero solo sobre subconjuntos más pequeños, de como máximo vértices. Informalmente, un expansor de conjunto pequeño es un gráfico cuya expansión de conjunto pequeño es grande. ^{[1] [c]} ${\displaystyle n}$ ${\displaystyle n/2}$ ${\displaystyle n/\log _{2}n}$

Declaración

La hipótesis de la expansión de conjuntos pequeños utiliza un número real como parámetro para formalizar lo que significa que la expansión de conjuntos pequeños de un gráfico sea grande o pequeña. Afirma que, para cada , es NP-difícil distinguir entre -gráficos regulares con expansión de conjuntos pequeños al menos (buenos expansores de conjuntos pequeños) y -gráficos regulares con expansión de conjuntos pequeños como máximo (muy lejos de ser un expansor de conjuntos pequeños) ). Aquí, el grado es una variable que podría depender de la elección de , a diferencia de muchas aplicaciones de gráficos de expansión donde se supone que el grado es una constante fija. ^{[1] [c]} ${\displaystyle \varepsilon }$ ${\displaystyle \varepsilon >0}$ ${\displaystyle d}$ ${\displaystyle (1-\varepsilon )d}$ ${\displaystyle d}$ ${\displaystyle \varepsilon d}$ ${\displaystyle d}$ ${\displaystyle \varepsilon }$

Consecuencias

La hipótesis de la expansión de conjuntos pequeños implica la dureza NP de varios otros problemas computacionales. Debido a que es sólo una hipótesis, esto no prueba que estos problemas sean realmente NP-difíciles. Sin embargo, sugiere que sería difícil encontrar una solución eficiente para estos problemas, porque resolver cualquiera de ellos también resolvería otros problemas cuya solución hasta ahora ha sido difícil de alcanzar (incluido el propio problema de expansión de conjuntos pequeños). En la otra dirección, esta implicación abre la puerta a refutar la hipótesis de la expansión de conjuntos pequeños, al plantear otros problemas a través de los cuales podría atacarse. ^[1]

En particular, existe una reducción del tiempo polinómico desde el reconocimiento de expansores de conjuntos pequeños hasta el problema de determinar el valor aproximado de juegos únicos, lo que demuestra que la hipótesis de la expansión de conjuntos pequeños implica la conjetura de los juegos únicos . ^{[1] [2]} Boaz Barak ha sugerido con más fuerza que estas dos hipótesis son equivalentes. ^[1] De hecho, la hipótesis de la expansión de conjuntos pequeños es equivalente a una forma restringida de la conjetura de los juegos únicos, afirmando la dureza de las instancias de juegos únicos cuyos gráficos subyacentes son expansores de conjuntos pequeños. ^[3] Por otro lado, es posible resolver rápidamente instancias de juegos únicos cuyo gráfico es "certificablemente" un pequeño expansor de conjuntos, en el sentido de que su expansión puede verificarse mediante optimización de suma de cuadrados . ^[4]

Otra aplicación de la hipótesis de la expansión de conjuntos pequeños se refiere al problema computacional de aproximar el ancho de árbol de los gráficos, un parámetro estructural estrechamente relacionado con la expansión. Para gráficos de ancho de árbol , la mejor relación de aproximación conocida para un algoritmo de aproximación de tiempo polinomial es . ^[5] La hipótesis de expansión de conjuntos pequeños, de ser cierta, implica que no existe un algoritmo de aproximación para este problema con relación de aproximación constante. ^[6] También se puede utilizar para implicar la inaproximabilidad de encontrar un gráfico bipartito completo con el número máximo de aristas (posiblemente restringido a tener el mismo número de vértices en cada lado de su bipartición) en un gráfico más grande. ^[7] ${\displaystyle w}$ ${\displaystyle O({\sqrt {\log w}})}$

La hipótesis de expansión de conjuntos pequeños implica la optimidad de relaciones de aproximación conocidas para ciertas variantes del problema de cobertura de aristas , en el que se deben elegir la menor cantidad de vértices posible para cubrir un número determinado de aristas en un gráfico. ^[8]

Historia y resultados parciales

La hipótesis de la expansión de conjuntos pequeños fue formulada y conectada con la conjetura de los juegos únicos por Prasad Raghavendra y David Steurer en 2010, ^[2] como parte de un trabajo por el que recibieron el Premio Michael y Sheila Held del Premio Nacional 2018. Academia de Ciencias . ^[9]

Un enfoque para resolver la hipótesis de la expansión de conjuntos pequeños es buscar algoritmos de aproximación para la expansión de bordes de conjuntos de vértices pequeños que sean lo suficientemente buenos para distinguir las dos clases de gráficos en la hipótesis. Desde este punto de vista, la mejor aproximación conocida, para la expansión de aristas de subconjuntos de como máximo vértices en un gráfico regular, tiene una relación de aproximación de . Esto no es lo suficientemente fuerte como para refutar la hipótesis; hacerlo requeriría encontrar un algoritmo con una relación de aproximación acotada. ^[10] ${\displaystyle n/\log n}$ ${\displaystyle d}$ ${\displaystyle O({\sqrt {\log n\log \log n}})}$

Notas

1. Esta definición sigue la notación utilizada en el artículo sobre el gráfico de expansión ; algunas fuentes, como Raghavendra y Steurer (2010), normalizan la expansión del borde dividiéndola por el grado del gráfico.
2. Esta definición evita el uso de subconjuntos cuyo número de vértices sea cercano a , porque estos subconjuntos tendrían una pequeña expansión incluso en gráficos que de otro modo tendrían una alta expansión. ${\displaystyle n}$
3. Esta formulación es de Barak (2016), quien señala que elimina algunos parámetros sin importancia que aparecen en otras formulaciones de la misma hipótesis, como la de Raghavendra y Steurer (2010).

Referencias

1. Barak, Boaz (2016), "Conferencia SOS 6: El enfoque SOS para refutar el UGC" (PDF) , notas de la conferencia sobre "Pruebas, creencias y algoritmos a través de la lente de la suma de cuadrados" , consultado el 14 de marzo de 2023
2. Raghavendra, Prasad; Steurer, David (2010), "Graph Expansion and the Unique Games Conjecture", en Schulman, Leonard J. (ed.), Actas del 42º Simposio ACM sobre Teoría de la Computación, STOC 2010, Cambridge, Massachusetts, EE. UU., 5– 8 de junio de 2010 (PDF) , Association for Computing Machinery, págs. 755–764, doi :10.1145/1806689.1806792, S2CID  1601199
3. Raghavendra, Prasad; Steurer, David; Tulsiani, Madhur (2012), "Reducciones entre problemas de expansión", Actas de la 27ª Conferencia sobre Complejidad Computacional, CCC 2012, Oporto, Portugal, 26 al 29 de junio de 2012 , IEEE Computer Society, págs. 64–73, arXiv : 1011.2586 , doi :10.1109/CCC.2012.43
4. Bafna, Mitali; Barac, Booz ; Kothari, Pravesh K.; Schramm, Tselil; Steurer, David (2021), "Jugar juegos únicos en expansores de conjuntos pequeños certificados", en Khuller, Samir ; Williams, Virginia Vassilevska (eds.), STOC '21: 53.º Simposio anual ACM SIGACT sobre teoría de la informática, evento virtual, Italia, 21 al 25 de junio de 2021 , Asociación de Maquinaria de Computación, págs. 1629-1642, arXiv : 2006.09969 , doi :10.1145/3406325.3451099
5. Feige, Uriel ; Hajiaghayi, Mohammadtaghi ; Lee, James R. (2008), "Algoritmos de aproximación mejorados para separadores de vértices de peso mínimo", SIAM Journal on Computing , 38 (2): 629–657, doi :10.1137/05064299X, MR  2411037
6. Wu, Yu; Austrian, Per; Pitassi, Toniann ; Liu, David (2014), "Inaproximabilidad del ancho de los árboles, guijarros de un solo disparo y problemas de diseño relacionados", Journal of Artificial Intelligence Research , 49 : 569–600, doi : 10.1613/jair.4030 , MR  3195329
7. Manurangsi, Pasin (2018), "Inaproximabilidad de problemas bicliques máximos, corte k mínimo y subgrafo al menos k más denso de la hipótesis de expansión de conjuntos pequeños", Algoritmos , 11 (1): P10:1 – P10:22 , arXiv : 1705.03581 , doi : 10.3390/a11010010 , SEÑOR  3758880
8. Gandhi, Rajiv; Kortsarz, Guy (2015), "Sobre los problemas de expansión de conjuntos y la conjetura de la expansión de conjuntos pequeños" (PDF) , Matemáticas Aplicadas Discretas , 194 : 93–101, doi :10.1016/j.dam.2015.05.028, MR  3391764
9. Premio Michael y Sheila 2018: Prasad Raghavendra y David Steurer, Academia Nacional de Ciencias , consultado el 23 de noviembre de 2023
10. Bansal, Nikhil; Feige, Uriel ; Krauthgamer, Robert; Makarychev, Konstantin; Nagarajan, Viswanath; Naor, José ; Schwartz, Roy (2014), "Partición de gráficos mínimo-máximo y expansión de conjuntos pequeños" (PDF) , SIAM Journal on Computing , 43 (2): 872–904, doi :10.1137/120873996, MR  3504685