Co wiadomo na temat przejścia fazowego w problemach # P-Complete? W szczególności, czy istnieje inne przejście fazowe dla # DNF-k-SAT i # CNF-k-SAT?
Aktualizacja:
Jak wiemy, w Random k-SAT występuje przejście fazowe, w którym rozwiązanie problemu staje się łatwe i trudne. Chciałbym również wiedzieć, czy istnieje takie zjawisko w przypadku problemów z # P-Complete. Co ważniejsze, jeśli istnieje przejście fazowe, czy to samo dla # CNF-k-SAT i # DNF-k-SAT?
Myślę, że dla # CNF-k-SAT istnieje pewien rodzaj przejścia fazowego. Z drugiej strony nie wydaje mi się, że dla # DNF-k-SAT występuje przejście fazowe i problem staje się trudniejszy, gdy dodajemy więcej klauzul ...
1
Czy mógłbyś wyjaśnić, co rozumiesz przez „przejście” fazy #P? Przejście fazowe dla problemów z NP-Complete jest zwykle uważane za prawdopodobieństwo przypadkowego wystąpienia losowego z pewnego sparametryzowanego rozkładu, który jest satysfakcjonujący (powiedzmy dla 3-SAT). Jakie jest przejście dla #P? Kiedy określony odsetek jest zadowalający?
—
user834,
Podaj również, czy próbujesz obliczyć dokładną wartość, czy dopuszczasz wartości przybliżone.
—
Tyson Williams,
„problem zmienia się z łatwego w trudny i znów w trudny”. Masz na myśli „łatwy w trudny i znowu łatwy”?
—
Tyson Williams,
Nadal nie jestem pewien, jaką ilość mierzysz. Przejście fazowe 3-SAT (jako przykład konkretności) jest traktowane jako prawdopodobieństwo istnienia rozwiązania. tj. co najmniej jednego istniejącego rozwiązania. Jeśli więc „przejście” #P oznacza prawdopodobieństwo niezerowej liczby rozwiązań, wówczas te dwa są równoważne. Istnieje również różnica między „łatwym” a „istniejącym rozwiązaniem”, ponieważ pierwszy z nich zakłada algorytm wielomianowy, a drugi nie. Elektrownia jądrowa jest znana z tego, że jest trudna niemal wszędzie, nawet daleko od punktu przejściowego.
—
user834,