Co wiemy na temat przejścia fazowego problemów # P-Complete?

11

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

cc.complexity-theory counting-complexity phase-transition Tayfun Pay
źródło
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,
1
„problem zmienia się z łatwego w trudny i znów w trudny”. Masz na myśli „łatwy w trudny i znowu łatwy”?
Tyson Williams,
1
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,

Odpowiedzi:

7

Do zliczania zestawów niezależnych istnieje najnowszy dowód na obliczeniowe przejście fazowe, autorstwa Allana Sly'ego: http://arxiv.org/abs/1005.5584 (algorytm opracowany przez Drora Weitza z 2006 r .; Allan udowodnił, że jest dopasowany do twardości i został zwycięzcą najlepsza nagroda papierowa w FOCS'10 za to)

Zauważ, że dla losowych 3SAT i podobnych problemów nie ma dowodów, że problemy te są rzeczywiście trudne w odpowiednim przedziale. Kiedy przejdziesz do trudniejszych problemów z liczeniem, łatwiej będzie udowodnić twardość.

Dana Moshkovitz
źródło