¿Qué sabemos sobre la transición de fase de los problemas # P-Complete?

11

¿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 ...

Tayfun Pay
fuente
1
¿Podría aclarar un poco lo que quiere decir con "la" transición de fase #P? La transición de fase para los problemas de NP-Complete generalmente se toma como la probabilidad de que una instancia aleatoria extraída de alguna distribución parametrizada sea satisfactoria (por ejemplo, 3-SAT). ¿Cuál es la transición para #P? ¿Cuándo un cierto porcentaje es satisfactorio?
user834
Especifique también si está tratando de calcular el valor exacto o si está permitiendo valores aproximados.
Tyson Williams
1
"el problema pasa de ser fácil a difícil y de nuevo a difícil" ¿Quieres decir "fácil a difícil y de nuevo a fácil"?
Tyson Williams el
1
Todavía no tengo claro qué cantidad es lo que está midiendo. La transición de fase 3-SAT (como ejemplo de concreción) se considera la probabilidad de que exista una solución. es decir, de al menos una solución existente. Entonces, si se considera que "la" transición #P significa la probabilidad de un recuento de soluciones distinto de cero, entonces esas dos son equivalentes. Además, existe una diferencia entre "fácil" y "una solución existente", ya que el primero implica un algoritmo polinómico mientras que el segundo no. NPP es conocido por ser difícil en casi todas partes, incluso lejos del punto de transición.
user834

Respuestas:

7

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.

Dana Moshkovitz
fuente