¿Algoritmo determinista paralelo para una coincidencia perfecta en gráficos generales?

20

En la clase de complejidad , se conjetura que algunos problemas NO están en la clase N C , es decir, problemas con algoritmos deterministas paralelos. El problema del flujo máximo es un ejemplo. Y se cree que hay problemas en N C , pero todavía no se encuentra una prueba.PNCNC

Coincidencia perfecta problema es uno de los problemas más fundamentales planteadas en la teoría de grafos: dado un grafo , tenemos que encontrar una correspondencia perfecta para G . Como pude encontrar en Internet, a pesar del hermoso algoritmo de tiempo polinómico Blossom de Edmonds, y un algoritmo paralelo ALEATORIZADO de Karp, Upfal y Wigderson en 1986, se sabe que solo unas pocas subclases de gráficos tienen algoritmos N C.GGNC

En enero de 2005, es un post en el blog de la complejidad computacional que las reclamaciones que permanece abierta si la coincidencia perfecta está en . Mi pregunta es:NC

¿Hay algún progreso desde entonces, más allá del algoritmo aleatorio ?NC

Para aclarar mi interés, cualquier algoritmo que trate con gráficos GENERALES es bueno. Aunque los algoritmos para subclases de gráficos también están bien, eso puede no estar en mi atención. ¡Gracias a todos!


EDITAR el 27/12:

Gracias por toda su ayuda, trato de resumir todos los resultados en una figura: Relaciones entre clases relacionadas con Matching

Las clases más bajas conocidas contienen los siguientes problemas:

  • Coincidencia en gráficos generales: [ KUW86 ], R N C 2 [ CRS93 ]RNCRNC2
  • Coincidencia en gráficos bipartitos planos / constantes de género: / S P L [ DKT10 ] / [ DKTV10 ]ULSPL
  • Coincidencia cuando el número total es polinomial: [ H09 ]SPL
  • Lex-primera coincidencia máxima: [ MS89 ]CC

Además, bajo un supuesto de complejidad plausible: requiere circuitos exponenciales, la correspondencia en gráficos generales está en S P L [ ARZ98 ].SPACE[n]SPL

Hsien-Chih Chang 張顯 之
fuente
1
Quizás no sea directamente relevante, pero ha habido algún progreso en los algoritmos deterministas para contar el número de coincidencias perfectas, es decir, el "Algoritmo de aproximación determinista de Gamarnik para calcular un permanente de una matriz de 0,1"
Yaroslav Bulatov
2
Hay una publicación relacionada aquí por Robin Kothari: cstheory.stackexchange.com/questions/1317/…
Hsien-Chih Chang 張顯 之
@ Hsien-ChihChang 張顯 之 ¿No está L en NC que está en NC ^ 2 que está en P?
T ....

Respuestas:

13

NC

NC2

NCPNCNC

ULNCULNC

Espero que esto ayude.

Ramprasad
fuente
1
Sí, me he dado cuenta del resultado por Vinodchandran-Tewari. De hecho, esta publicación está motivada por su resultado de alguna manera, aunque no directamente. ¡Revisaré el periódico de Agrawal-Hoang-Thierauf!
Hsien-Chih Chang 張顯 之
10

Unos años más tarde :) y Perfect Matching ahora se sabe que está en Cuasi-NC (es decir, necesita casi muchos procesadores polinomialmente). Consulte el documento de Fenner, Gurjar y Thierauf (para gráficos bipartitos) https://arxiv.org/pdf/1601.06319.pdf y nuestro trabajo con Ola Svensson (para gráficos generales): https://arxiv.org/pdf/1704.01929

Jakub Tarnawski
fuente
8

La desrandomización del lema de aislamiento por Tewari-Vinodchandran no da un límite superior UL en la coincidencia plana desafortunadamente. De hecho, ni siquiera creo que un algoritmo NC no sea conocido por la coincidencia plana. Pero en un trabajo reciente con Datta, Kulkarni y Nimbhorkar mostramos un límite superior de UL en la coincidencia plana bipartita (la revisión de este resultado aún está en progreso). Esto es interesante porque antes de esto, incluso un límite de NL no era conocido por este problema.

Raghunath Tewari
fuente
¡Bienvenido a TCS Stack Exchange!
Hsien-Chih Chang 張顯 之
Ahora encontré el periódico de Datta, Kulkarni y tú. Lo leeré lo antes posible, ¡Gracias!
Hsien-Chih Chang 張顯 之
7

Cuando se sabe que un problema de optimización es difícil, es habitual mirar sus versiones máximas. Por ejemplo, mientras que el conjunto independiente es NP-Completo, el primer conjunto independiente máximo lex, que es P-Completo.

n

Todos estos puntos dicen que puede que no haya una versión NC fácilmente paralelizable para esto. Pero entonces, ¿quién sabe? ¡Alguien puede desrandomizar la versión RNC la próxima semana!

Editar: Gracias Ramprasad. Pero aquí hay otro enlace al documento.

V Vinay
fuente
1
Vaya, no tengo cuenta para acceder al periódico. ¿Cuál es el título de la misma?
Hsien-Chih Chang 張顯 之
1
"La complejidad del valor del circuito y la estabilidad de la red". He puesto una copia del documento aquí: cmi.ac.in/~ramprasad/00041817.pdf (¡espero que no haya problemas de derechos de autor!)
Ramprasad
1

(1ϵ)NCnΘ(1/ϵ)O(log3n)

T. Fischer, AV Goldberg, DJ Haglin y S. Plotkin. Aproximación de coincidencias en paralelo. Info. Proc. Lett., 46 (3): 115, 1993

Mohammad Al-Turkistany
fuente