Pytania otagowane jako counting-complexity

Jak trudno policzyć liczbę rozwiązań?

1
Więcej na temat PH w PP?
Ostatnie pytanie za pytaniem, czy Huck Bennett PH klasa została zawarta w PP klasy, otrzymał nieco sprzecznych odpowiedzi (wszystko prawda, wydaje się). Z jednej strony podano przeciwnie kilka wyników wyroczni, z drugiej Scott zasugerował, że odpowiedź jest prawdopodobnie pozytywna, ponieważ twierdzenie Tody pokazuje, że PH jest w BP.PP, wariancie probabilistycznym …
3
Zaskakujące algorytmy liczenia problemów
Istnieją pewne problemy z liczeniem, które polegają na zliczaniu wykładniczo wielu rzeczy (w stosunku do wielkości danych wejściowych), a jednak mają zaskakujące algorytmy deterministyczne o czasie wielomianowym. Przykłady obejmują: Zliczanie idealnych dopasowań na wykresie planarnym ( algorytm FKT ), który jest podstawą działania algorytmów holograficznych . Zliczanie drzew rozciągających się …
4
Czy ?
Wiemy, że pierwszy poziom hierarchii wielomianowej (tj. NP i co-NP) znajduje się w PP i że . Wiemy również z twierdzenia Tody, że .PP⊆PSPACEPP⊆PSPACEPP \subseteq PSPACEPH⊆PPPPH⊆PPPPH \subseteq P^{PP} Czy wiemy, czy ? Jeśli nie, to dlaczego z wyrocznią jest silniejszy niż ? Czy to możliwe, że i PP \ nsubseteq …
2
Jak trudno policzyć liczbę czynników całkowitych?
Biorąc pod uwagę liczbę całkowitą długości n bitów, jak trudne jest wyprowadzenie liczby czynników pierwszych (lub alternatywnie liczby czynników) N ?N.NNnnnN.NN Gdybyśmy znali podstawową faktoryzację , byłoby to łatwe. Gdybyśmy jednak znali liczbę czynników pierwszych lub liczbę czynników ogólnych, nie jest jasne, w jaki sposób ustalilibyśmy faktyczne czynniki pierwsze.NNN Czy …
2
Kiedy „X jest kompletne NP” oznacza, że ​​„# X jest kompletne P”?
Niech oznacza problem (decyzji) w NP, a # oznacza jego wersję zliczającą.XXXXXXX 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 …
3
Kiedy odprężenie się liczy?
Załóżmy, że rozwiązujemy problem zliczania prawidłowych zabarwień, licząc ważone zabarwienia w następujący sposób: każde prawidłowe zabarwienie otrzymuje wagę 1, a każde niewłaściwe zabarwienie otrzymuje wagę gdzie jest w pewnym stopniu stałe, a to liczba krawędzi z punktami końcowymi ma ten sam kolor. Gdy zmienia się na 0, sprowadza się to …
2
Złożoność obliczeniowa liczników indukowanych liczeniem, które dopuszczają idealne dopasowanie
Biorąc pod uwagę nieukierunkowany i nieważony wykres a jeszcze całkowita k , co jest złożoność obliczeniowa zestawów zliczania wierzchołków S ⊆ V tak, że | S | = k, a podgrupa G ograniczona do zbioru wierzchołków S dopuszcza idealne dopasowanie? Czy złożoność # P jest kompletna? Czy istnieje odniesienie do …
2
Czy istnieje bezpośrednia / naturalna redukcja, aby liczyć niedwustronne idealne dopasowania za pomocą stałego?
Zliczanie liczby idealnych dopasowań na wykresie dwustronnym można natychmiast zredukować do obliczenia wartości stałej. Ponieważ znalezienie idealnego dopasowania na grafie dwustronnym występuje w NP, istnieje pewna redukcja z grafów dwustronnych do stałych, ale może to wiązać się z nieprzyjemnym wielomianowym powiększeniem poprzez zastosowanie redukcji Cooka do SAT, a następnie twierdzenia …
5
Łatwe problemy z trudnymi do zliczenia wersjami
Wikipedia podaje przykłady problemów, w których liczenie wersji jest trudne, natomiast wersja decyzyjna jest łatwa. Niektóre z nich liczą doskonałe dopasowania, licząc liczbę rozwiązań SAT i liczbę sortowań topologicznych.222 Czy są jeszcze jakieś inne ważne klasy (powiedzmy przykłady z sieci, drzew, teorii liczb i tak dalej)? Czy istnieje kompendium takich …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.