Powyżej #P i liczenie problemów z wyszukiwaniem

Czytałem artykuł na Wikipedii o problemie ośmiu królowych. Stwierdzono, że nie ma znanego wzoru na dokładną liczbę rozwiązań. Po kilku poszukiwaniach znalazłem artykuł o twardości liczenia problemów z kompletnymi mapowaniami. W tym artykule jest problem, który okazuje się co najwyżej tak trudny jak #kolory, który jest większy niż #P. Rzucając okiem na liczbę znaków #queens liczonych wyczerpująco w artykule na Wikipedii, wydają się one bardzo wykładnicze.

Chcę zapytać, czy istnieje nazwa dla tej klasy lub czy ogólnie występują problemy z liczeniem należące do klas powyżej #P (z decyzją nie w PSPACE oczywiście, ponieważ byłoby to oczywiste).

Na koniec chcę zapytać, czy są jakieś inne znane wyniki dla innych problemów z wyszukiwaniem, na przykład znalezienie trójkolorowego punktu w Lemmie Spernera (ukończenie PPAD).

Jeżeli funkcja f jest #p, to biorąc pod uwagę ciąg znaków X pewnej długości N wartość f (x) jest liczbą dodatnią ograniczony . (Wynika to z definicji pod względem liczby ścieżek akceptacji weryfikatora NP.)$2^{poly(N)}$

Oznacza to, że wiele funkcji f leżą poza #p do nieciekawe powodów --- albo ponieważ f ma wartość ujemną, lub, w przypadku, gdy wymieniona, ponieważ funkcja rośnie szybciej niż . Ale w przypadku problemu n- znaków według modelu, jest to tylko artefakt decyzji autorów, aby wartość wejściowa n była zakodowana w postaci binarnej. Jeśli oczekiwanym wejściem był łańcuch jednoargumentowy 1 n , to f ( 1 n ) : = (liczba prawidłowych $2^{poly(N)}$$n$$n$$1^n$$f(1^n) :=$$n$-kolejne konfiguracje) z pewnością będzie w #P, przez prostego weryfikatora NP, który sprawdza poprawność danej konfiguracji.

Jeśli chcesz poznać niektóre funkcje, które (przypuszczalnie) leżą poza #P z bardziej interesujących powodów, rozważ np. Te:

• UNSAT: jeśli ψ jest niezadowalającą formułą logiczną, w przeciwnym razie f ( ψ ) : = 0 . Ta funkcja nie znajduje się w #P, chyba że NP = coNP. Prawdopodobnie nie należy do bardziej ogólnej klasy liczenia GapP; to znaczy, UNSAT prawdopodobnie nie jest różnicą f - g dwóch funkcji #P. Jednak leży ona w bardziej ogólnej klasie złożoności liczenia P # P , która w rzeczywistości zawiera całą hierarchię wielomianową według twierdzenia Tody.$f(\psi) := 1$$\psi$$f(\psi) := 0$$P^{\# P}$

Może ci się nie podobać ten przykład, ponieważ nie jest to naturalny „problem z liczeniem”. Ale następne dwa będą:

• liczba przypisań do x, tak że formuła logiczna ψ ( x , ⋅ ) jest zadowalająca dla niektórych ustawień y .$f(\psi(x, y)) :=$$x$$\psi(x, \cdot)$$y$

• ilość x, tak, że co najmniej połowa wszystkich Y , ψ ( x , y ) = 1 .$f(\psi(x, y)) :=$$x$$y$$\psi(x, y) = 1$

Te dwa ostatnie problemy nie są wydajnie obliczalne, nawet z dostępem Oracle do #P. Można je jednak obliczać w ramach tak zwanej „hierarchii liczenia”. Niektóre bardziej naturalne problemy sklasyfikowane w tej klasie, patrz np. Ten ostatni artykuł.

Liczenie równowagi Nasha jest najwyraźniej trudniejsze niż P, patrz tutaj . Również problemy, w których problem wyszukiwania jest łatwy, mogą być trudne do policzenia, np. Liczenie idealnych dopasowań.

Oprócz przyjętej odpowiedzi, oto niedawny artykuł (grudzień 14) na temat złożoności liczenia niektórych ograniczonych modeli logiki czasowej w czasie. Wyższe i bardziej ezoteryczne klasy złożoności są obecne w pokazanych wynikach: warianty problemu to -kompletny, # E X P T I M E -kompletny itp.$\#PSPACE$$\#EXPTIME$

Złożoność modeli liczenia logiki czasowej w czasie liniowym Hazem Torfah, Martin Zimmermann