Encuesta sobre #P y / o problemas de conteo

23

¿Alguien puede sugerir una encuesta buena y reciente sobre problemas de conteo y / o problemas que son #P.

cc.complexity-theory reference-request counting-complexity Tayfun Pay
fuente
Estos documentos parecen ser pocos y distantes entre sí. Estaría muy interesado en una buena encuesta sobre el tema. Noté que Wikipedia ni siquiera contiene una "Lista de # problemas P-completos". También es interesante que haya 3 preguntas hoy que soliciten referencias para contar problemas.
bbejot 05 de

Respuestas:

13

L. Fortnow. Contando la complejidad . En L. Hemaspaandra y A. Selman, editores, Complexity Theory Retrospective II, páginas 81-107. Springer, 1997

Esto proporciona más del punto de vista de la complejidad estructural (clases de complejidad, oráculos, etc.) y discute otras clases relacionadas con #P. Aunque es desde hace casi 15 años, en realidad no es que fuera de la fecha en términos de resultados.

Joshua Grochow
fuente
1
@Tayfun: ¿Qué falta? No es que no esté necesariamente en desacuerdo con usted, solo tengo curiosidad por saber qué le gustaría ver además.
Joshua Grochow
9

Pinyan Lu publicó una encuesta través de ECCC a mediados de 2011. Compara tres marcos de conteo populares:

  • Contando Homomorfismos Gráficos,
  • Conteo de satisfacción de restricciones (#CSP), y
  • el marco Holant
  • (y restricciones de estos marcos).

También discute los teoremas de dicotomía actuales y las técnicas de prueba utilizadas para obtenerlos.

Xi Chen publicó una encuesta como columna invitada para SIGACT News a fines de 2011. Discute los resultados y las técnicas que condujeron a sus documentos con Jin-Yi Cai y Pinyan Lu e incluyeron sus dicotomías para contar los homomorfismos de gráfico definidos por un gráfico objetivo no dirigido con ponderaciones complejas ( arXiv ) y #CSPs sin ponderación negativa ( arXiv ).

Aproximadamente al mismo tiempo, Cai y Chen publicaron una dicotomía para #CSPs ( arXiv ) ponderados de forma compleja , que Cai discutió en una publicación invitada en el blog Godel's Lost Letter y P = NP .

Tyson Williams
fuente
¡Agradable! ¡Leeré esto!
Tayfun Pay
3

Otro marco de problemas de conteo proviene de calcular el polinomio de Tutte de un gráfico. En este marco, dos números complejos definen un problema de conteo.

El libro Matroid Applications dedica el capítulo 6 a El polinomio de Tutte y sus aplicaciones . El enlace anterior es un escaneo de ese capítulo desde el sitio web de James Oxley , uno de los coautores. El semestre pasado, enseñó un curso basado en ese capítulo.

Otra buena referencia sobre este tema es este documento tipo encuesta de Welsh.

Tyson Williams
fuente