Powodem, dla którego nie jest to automatyczne twierdzenie, że „decyzja jest trudna, implikuje, że liczenie jest trudne”, wynika z faktu, że te dwie wypowiedzi używają różnych definicji „twardego”.
Problem decyzyjny jest trudny, jeśli jest zakończony NP przy wielomianowych redukcjach w czasie wielu-jeden (aka redukcji Karp, aka redukcji mapowania w czasie wielomianowym).
Problem z liczeniem jest trudny, jeśli jest zakończony #P przy wielomianowych redukcjach Turinga ( zwanych również redukcjami Cooka).
W związku z tym, jeśli problem decyzyjny jest NP-zupełny , wiemy, że odpowiadający mu problem zliczania to NP- twardy, ale to nie jest definicja trudnego problemu zliczania. Bycie # P-kompletnym wydaje się być znacznie silniejszym stwierdzeniem niż tylko bycie NP- twardym - Toda pokazał, że problemy z # P-uzupełnieniem są trudne dla całej hierarchii wielomianowej przy losowych redukcjach, więc jako klasa złożoności #P wydaje się być znacznie bliższy do PSPACE niż do NP .
Idąc w kierunku przeciwnym, to oczywiście prawdą, że jeśli problem liczenia jest łatwy w sensie bycia w FP , to problem jest decyzja w P . W końcu, jeśli potrafisz skutecznie liczyć, z pewnością możesz stwierdzić, czy odpowiedź jest niezerowa. Jednak fakt, że liczenie wersji nie jest „trudne” (tj. Nie # -kompletny ), nie oznacza, że jest „łatwy” (tj. W FP ). Twierdzenie Ladnera rozciąga się na #P, więc jeśli FP≠** # P ** wtedy istnieje nieskończona hierarchia odrębnych klas złożoności między nimi, więc nasz „trudny” problem zliczania może być kompletny dla dowolnej z tych klas, a zatem nie będzie „łatwy” (w FP ).
Powiedziawszy to, nie sądzę, abyśmy mieli jakieś kontrprzykłady w przypuszczeniu, że problem decyzyjny jako NP-zupełny oznacza, że wersja licząca jest #P -kompletna . Nie jest to więc twierdzenie, ale jest empirycznie prawdziwe.
