# P-kompletny problem, którego wersja decyzji jest w P

14

1) Czy możliwe jest oszczędne zmniejszenie z problemu # P-zupełnego #A do problemu zliczania #B, gdy (wersja decyzyjna) A jest NP-kompletna, a B jest w P?

Na przykład, czy może wystąpić oszczędne obniżenie z #SAT do #B, gdy B jest w P?

2) Jeśli B jest w P, jakie są różne możliwości złożoności #B?

cc.complexity-theory complexity-classes counting-complexity marjoonjan
źródło

20

$F$ $G$ $2^{8m}+1$ $4^m$ $F$ $m$ $F$ $F$ $G$ .

Zobacz rozdział 18 w książce Papadimitriou „Złożoność obliczeniowa”, aby uzyskać jasne wyjaśnienie tego.

slimton
źródło

7

Odpowiedź na pytanie 2 jest taka, że złożoność problemu liczenia #B może być zasadniczo wszystkim (nawet niekoniecznie obliczalnym). Dokładniej, ograniczenie, że wersja decyzji znajduje się w P, nie ma żadnego wpływu na złożoność wersji zliczającej. Wynika to z faktu, że można dodać fikcyjne rozwiązanie do dowolnego problemu z relacjami, aby wersja decyzyjna stała się trywialna (odpowiedź zawsze brzmi „tak”) bez zmiany złożoności wersji zliczającej.

Tsuyoshi Ito
źródło

1

dlaczego tak mówisz? ”(nawet niekoniecznie obliczalny)„ Oczywiste jest, że jeśli B jest problemem decyzyjnym w P, to #B jest w #P, bezpośrednio z definicji klasy #P! ale udowodnienie, że #B jest również # P-com jest ważne, a dodanie fałszywych rozwiązań nie powinno mieć wpływu na złożoność liczenia. zgadzasz się?

marjoonjan,

@marjoonjan: „Oczywiste jest, że jeśli B jest problemem decyzyjnym w P, to #B znajduje się w #P, bezpośrednio z definicji klasy #P” To nieprawda. Mam również wrażenie, że uważasz, że problem decyzyjny B jednoznacznie determinuje problem liczenia #B, ale tak nie jest, jak wyjaśniłem w tej odpowiedzi.

Tsuyoshi Ito,

# P-kompletny problem, którego wersja decyzji jest w P

Odpowiedzi: