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 ?f : { 0 , 1 } ∗ → N X s f ( s ) ≠ $X$$f : \{0,1\}^* \to \mathbb{N}$$X$$s$$f(s) \ne 0$

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

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}}$