Kiedy „X jest kompletne NP” oznacza, że „# X jest kompletne P”?

Niech oznacza problem (decyzji) w NP, a # oznacza jego wersję zliczającą. $X$ $X$

Pod jakimi warunkami wiadomo, że „X to NP-zupełny” że „X jest kompletny? $\implies$

Oczywiście istnienie skąpej redukcji jest jednym z takich warunków, ale jest to oczywiste i jedyny taki warunek, o którym wiem. Ostatecznym celem byłoby wykazanie, że żaden warunek nie jest potrzebny.

Formalnie rzecz biorąc, należy zacząć od problemu liczenia # zdefiniowanego przez funkcję a następnie zdefiniować problem decyzyjny na ciągu wejściowym jako ? $X$ $f : \{0,1\}^* \to \mathbb{N}$ $X$ $s$ $f(s) \ne 0$

cc.complexity-theory np-hardness counting-complexity

— Tyson Williams
źródło

Czy szukasz czegoś więcej niż „X jest kompletny NP przy skąpej redukcji”?

— Joshua Grochow

@usul: Nie. Jeśli odrzucimy założenie, że X jest NP-zupełny, to dopasowanie dwustronne jest w P (więc zdecydowanie nie jest w zupełności NP-zupełny, zakładając, że ), ale jego wersja zliczająca to # P-complete. Jeśli jednak naprawdę chcemy X NP-zupełnego, to z góry mojej głowy nie znam problemu X takiego, że: 1) X jest NP-kompletny, 2) X nie jest NP-kompletny przy skąpych redukcjach, oraz 3) #X jest # P-kompletne. Ale tak naprawdę o tym nie myślałem.

P \neq N P

$P \neq NP$

— Joshua Grochow

Ale czy istnieje problem, który to neguje? tzn. X jest kompletne NP, a # X nie jest kompletne P?

— Suresh Venkat

@YoshioOkamoto: dowodzi, że #X ∈ #P oznacza, że X ∈ NP . Jest w złym kierunku i brakuje mu problemu kompletności. To, na co zasadniczo patrzymy, to jakie dodatkowe wymagania są potrzebne, aby istniała redukcja wiele do jednego w przypadku problemów decyzyjnych w NP (w przypadku problemów arbitralnych lub z problemu kompletnego NP ) pociąga za sobą istnienie efektywna redukcja zliczania dla problemów w #P (dla dowolnych problemów z liczeniem lub z problemów z uzupełnieniem #P ).

— Niel de Beaudrap

@ColinMcQuillan Można to stwierdzić na odwrót. Zacznij od problemu zliczania i zdefiniuj na nim problem decyzyjny, pytając, czy dane wyjściowe są niezerowe.

— Tyson Williams

Najnowszy artykuł na ten temat wydaje się:

Noam Livne, Notatka na temat # P-kompletności relacji między świadkami NP , Listy przetwarzania informacji, Tom 109, Numer 5, 15 lutego 2009 r., Strony 259–261 http://www.sciencedirect.com/science/article/pii/ S0020019008003141

co daje pewne wystarczające warunki.

Co ciekawe, wstęp mówi: „Do tej pory wszystkie znane kompletne zestawy NP mają relację definiującą, która jest #P ukończona”, więc odpowiedź na komentarz Suresha brzmi „nie są znane żadne przykłady”.

— Colin McQuillan
źródło

Fischer, Sophie, Lane Hemaspaandra i Leen Torenvliet. „Redukcje izomorficzne świadków i wyszukiwanie lokalne”. UWAGI WYKŁADOWE W CZYSTEJ I STOSOWANEJ MATEMATYCE (1997): 207-224.

Na początku sekcji 3.5 zadają następujące pytanie: „W szczególności, czy istnieją zestawy NP-zupełne, które w odniesieniu do niektórych schematów świadków nie są # -pełniane?”

$_L$ ${\bf P}$ $\not =$ ${\bf P^{\bf \#P}}$

— Tayfun Pay
źródło

Kiedy „X jest kompletne NP” oznacza, że ​​„# X jest kompletne P”?

Kiedy „X jest kompletne NP” oznacza, że „# X jest kompletne P”?