¿Qué se sabe sobre la transición de fase en problemas # P-Complete? Específicamente, ¿existe una transición de fase diferente para # DNF-k-SAT y # CNF-k-SAT?
Actualización:
Como sabemos, hay una transición de fase en Random k-SAT donde la resolución del problema pasa de ser fácil a difícil y volver a ser fácil nuevamente. Me gustaría saber si también existe un fenómeno para los problemas # P-Complete. Más importante aún, si existe una transición de fase, ¿es lo mismo para # CNF-k-SAT y # DNF-k-SAT?
Estoy pensando que hay algún tipo de transición de fase para # CNF-k-SAT. Por otro lado, no creo que haya una transición de fase para # DNF-k-SAT y el problema se vuelve más difícil a medida que agregamos más cláusulas ...
11
Respuestas:
Para contar conjuntos independientes, hay una prueba reciente de una transición de fase computacional, por Allan Sly: http://arxiv.org/abs/1005.5584 (el algoritmo es de Dror Weitz de 2006; Allan demostró la dureza correspondiente y co-ganó el mejor premio de papel en FOCS'10 por eso)
Tenga en cuenta que para 3SAT aleatorio y problemas similares no hay prueba de que esos problemas sean realmente difíciles en el intervalo apropiado. Cuando vas a los problemas de conteo más difíciles, se vuelve más fácil demostrar la dureza.
fuente