Dureza de aproximación sin el teorema de PCP

36

Una aplicación importante del teorema de PCP es que produce resultados de tipo "dureza de aproximación". En algunos casos relativamente más simples, se puede demostrar tal dureza sin PCP. Sin embargo, ¿existe algún caso en el que el resultado de la dureza de la aproximación se haya probado por primera vez utilizando el teorema de PCP, es decir, el resultado no se conocía antes, pero luego se encontró una prueba más directa que no depende de PCP? En otras palabras, ¿hay algún caso en el que PCP pareciera necesario primero, pero luego podría eliminarse?

cc.complexity-theory approximation-hardness pcp Andras Farago
fuente

35

Un ejemplo es este artículo:

Guruswami, V. y Khanna, S. (2004). Sobre la dureza de 4 colores, un gráfico de 3 colores. Revista SIAM sobre Matemáticas Discretas , 18 (1): 30-40. enlazar

Usando el teorema de PCP, Khanna, Linial y Safra (2000) demostraron que es NP-difícil colorear un gráfico de 3 colores usando solo 4 colores. Más tarde, Guruswami y Khanna (2004) dieron, entre otras cosas buenas, una prueba sin PCP para el mismo resultado.

vb le
fuente

11

¿Estaría dispuesto a describir el artículo en su respuesta, en lugar de solo señalarlo con un hipervínculo?

Niel de Beaudrap

15

Para el problema de las trayectorias disjuntas de borde máximo en los gráficos dirigidos, el artículo de Ma & Wang (2000) se basó en el problema de la cubierta de la etiqueta, que a su vez se basa en el teorema de PCP. Posteriormente, Guruswami et. Encontró una reducción simple a través de la dureza del problema 2- disjointpath. Alabama. (2003), que también proporcionó una mejor dureza.

Chandra Chekuri
fuente

¿Pero la dureza 2-disjointpath requiere la PCP?

Suresh Venkat

3

@SureshVenkat, 2-disjointpaths no requiere PCP. Es el problema de decidir si hay caminos disjuntos de conexión

y

en un gráfico dirigido

. Se demostró que NP-Complete a través de una intrincada reducción de gadgets de SAT, por Fortune, Hopcroft y Wylie.

(s_{1}, t_{1})

$(s_1,t_1)$

(s_{2}, t_{2})

$(s_2,t_2)$

G

$G$

Chandra Chekuri

13

Hay ejemplos de conteo aproximado. Contar aproximadamente el número de asignaciones satisfactorias de una relación NP solo puede ser más difícil que decidir si existe una asignación satisfactoria, por lo que no es demasiado sorprendente que uno no necesite el teorema de PCP para demostrar la dureza de tales problemas. Aún así, el teorema de PCP a veces proporciona un punto de partida conveniente, por ejemplo, para este artículo sobre aproximadamente contar el número de conjuntos independientes en un gráfico disperso: http://www.dcs.ed.ac.uk/home/mrj/papers/ DFJ02.pdf Más tarde, Sly demostró un resultado de dureza para contar aproximadamente conjuntos independientes basados en la dureza NP estándar de Max-Cut: http://arxiv.org/pdf/1005.5584v1.pdf

Dana Moshkovitz
fuente

1

d = 6

$d=6$

2

c

$c$

e^{c n}

$e^{cn}$

c

$c$

10

Otra respuesta, que tiene un espíritu algo diferente a las respuestas anteriores, es este artículo de Uri Feige: Relaciones entre la complejidad de los casos promedio y la complejidad de la aproximación .

Uri muestra que los supuestos de caso promedio pueden reemplazar el teorema de PCP para probar la dureza de la aproximación de algunos problemas. Sin embargo, tenga en cuenta que no sabemos cómo demostrar los supuestos de caso promedio, y tenemos algunas pruebas de que no podremos probarlos en base a supuestos de dureza NP estándar (consulte los documentos de Feigenbaum-Fortnow, Bogdanov-Trevisan, etc.).

Dana Moshkovitz
fuente

Dureza de aproximación sin el teorema de PCP

Respuestas: