Jaka jest złożoność obliczania liczby rozwiązań problemu P-Space Complete? Co powiesz na klasy o wyższej złożoności?

Chyba nazywa się to # P-Space, ale znalazłem tylko jeden artykuł niejasno o tym wspominając. Co powiesz na liczącą się wersję problemów EXP-TIME-Complete, NEXP-Complete oraz EXP-SPACE-Complete? Czy są jakieś wcześniejsze prace, które można przytoczyć w odniesieniu do tego lub dowolnego rodzaju włączenia lub wyłączenia, takiego jak Toda's Torem?

cc.complexity-theory complexity-classes counting-complexity pspace Tayfun Pay
źródło

Często zadajesz jedno pytanie!

Tsuyoshi Ito

#PSPACE to ta sama klasa co funkcje, które można obliczać w przestrzeni wielomianowej (FPSPACE).

Tsuyoshi Ito

@Tsuyoshi To prawda. Jednak większość pytań, jeśli nie wszystkie, można przeformułować jako jedno ogólne pytanie: Czy istnieją klasy liczące dla klas wyższych niż

(jak można zauważyć w definicji #

) i czy mają zastosowanie znane wyniki?

N P

$NP$

P

$P$

chazisop

@Tayfun Pay: Nie jestem do końca pewien, co masz na myśli dla klas deterministycznych, takich jak PSPACE, EXP, EXPSPACE. Pojęcie „liczby rozwiązań” jest zwykle ściśle związane z niedeterminizmem - od tego czasu można zapytać o liczbę ścieżek akceptacji - lub egzystencjalnych kwantyfikatorów / prognoz. W przypadku PSPACE można oczywiście zastosować definicję naprzemiennych kwantyfikatorów - ale wtedy trzeba określić, które kwantyfikatory chcesz policzyć - lub fakt, że NPSPACE = PSPACE.

Joshua Grochow

Jak wspomniano w kilku komentarzach, nie jest całkowicie jasne, co chciałbyś oznaczać dla #PSPACE. Najlepiej byłoby wziąć wyściełany analog #L, który jest dobrze zbadany. Ponieważ #L jest zawarty w DSPACE (log ^ 2 n), oznaczałoby to, że # PSPACE = PSPACE, jak wspomniano powyżej @TsuyoshiIto. (Ignoruję tutaj niematerialne formalne rozróżnienie między problemami decyzyjnymi a funkcjami).

Noam

Odpowiedzi:

-3

Liczba spełniających przypisań do formuły boolowskiej jest równa liczbie prawidłowych kwantyfikacji formuły. Indukcyjny dowód jest dość elegancki. Więc #P = #PSpace.

Daniel Pehoushek
źródło

Czy to nie jest objęte powyższymi komentarzami Tsuyoshi i Noama?

Huck Bennett,

Czy to naprawdę masz na myśli? Jeśli #P = #PSPACE, czy nie oznacza to, że PSPACE

? Nie wierzę, że to wiadomo.

\subseteq

$\subseteq$

^{# P}

$^{\#\mathrm{P}}$

Peter Shor,

@PeterShor Jestem całkiem pewien, że Daniel oznacza to mathoverflow.net/a/12608/35733 . Ale moje (niezweryfikowane) przypuszczenie jest takie, że # -pełnym problemem PSPACE jest policzenie liczby spełniających przypisań stałego QBF, a nie zliczenie liczby zadowalających kwantyfikacji danego CNF.

Sasho Nikolov,

Nie, miałem na myśli, że liczba prawidłowych kwantyfikacji danego cnf jest równa liczbie satysfakcjonujących przypisań cnf, biorąc pod uwagę ustaloną kolejność zmiennych. Bardzo interesujące jest to, że zmiana kolejności zmiennych zmienia prawidłowe qbfs, ale nie całkowitą liczbę prawidłowych qbfs.

Daniel Pehoushek