O que se sabe sobre a transição de fase nos problemas # P-Complete? Especificamente, existe uma transição de fase diferente para # DNF-k-SAT e # CNF-k-SAT?
Atualização:
Como sabemos, há uma transição de fase no Random k-SAT em que a solução do problema passa de fácil a difícil e volta a fácil novamente. Gostaria de saber se também existe esse fenômeno para os problemas do # P-Complete. Mais importante, se existe uma transição de fase, é o mesmo para # CNF-k-SAT e # DNF-k-SAT?
Eu estou pensando que existe algum tipo de transição de fase para o # CNF-k-SAT. Por outro lado, não acho que exista transição de fase para o # DNF-k-SAT e o problema fica mais difícil à medida que adicionamos mais cláusulas ....
11
Respostas:
Para a contagem de conjuntos independentes, há uma prova recente de uma transição de fase computacional, feita por Allan Sly: http://arxiv.org/abs/1005.5584 (o algoritmo é de Dror Weitz de 2006; Allan provou a dureza correspondente e co-venceu o prêmio de melhor artigo do FOCS'10 por isso)
Observe que, para problemas aleatórios do 3SAT e similares, não há provas de que esses problemas sejam realmente difíceis no intervalo apropriado. Quando você passa para os problemas de contagem mais difícil, fica mais fácil provar a dureza.
fonte