Zaskakujące algorytmy liczenia problemów

54

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ą:

Kluczowym krokiem w obu tych przykładach jest ograniczenie problemu zliczania do obliczenia wyznacznika określonej macierzy. Wyznacznik sam w sobie jest oczywiście sumą wykładniczo wielu rzeczy, ale może być niespodziewanie obliczony w czasie wielomianowym.

Moje pytanie brzmi: czy istnieją jakieś „zaskakująco skuteczne” dokładne i deterministyczne algorytmy znane z liczenia problemów, które nie ograniczają się do obliczenia wyznacznika?

Ashley Montanaro
źródło
8
BTW, wiele innych problemów z liczeniem sprowadza się do obliczania wyznacznika. Determinator liczb całkowitych jest kompletny dla klasy GapL, która zawiera #L.
5501

Odpowiedzi:

11

Nie wiem, czy następujące problemy ograniczają się do obliczenia wyznacznika, ale i tak wymienię:

1) Zliczanie liczby ścieżek w DAG od węzła do węzła . Ale to nie jest zaskakujące. Proste określenie, czy jest osiągalny z jest w NL, a zatem w DET . Nie mam pojęcia o wersji zliczającej.v0vfvfv0

2) Zliczanie liczby rozwiązań problemów definiowalnych w logice MSO w strukturach o ograniczonej szerokości drzewa. Zobacz na przykład artykuł na temat prac Courcelle, Arnborg i innych .

3) Jeśli masz funkcję , którą można wyrazić za pomocą obwodu bolean o szerokości drzewa logarytmicznego, niż możesz policzyć liczbę wejścia takie, że przez opracowanie obwodu kwantowego który wysyła do i klasycznie symuluje prawdopodobieństwo pomiaru w drugim rejestrze po zastosowaniu przy użyciu tych wyników .f:{0,1}n{0,1}xf(x)=1Uf|x|0|x|f(x)|1UfHn|0|0

Mateus de Oliveira Oliveira
źródło
Dzięki - elementy (2) i (3) są interesujące, ale jakoś nie do końca to, czego szukałem; problemy z liczeniem ograniczonej szerokości drzewa wydają się bardziej jak specjalne przypadki, w których struktura, z którą pracujesz, jest faktycznie ograniczona wielomianowo. Bardziej interesowały mnie przypadki, w których „naprawdę” wykładniczo jest wiele obiektów do policzenia, ale można je magicznie policzyć w czasie wielomianowym.
Ashley Montanaro,
Czy nie oznacza to, że jeśli zastosujesz jednoargumentowe kodowanie, algorytm potrzebuje czasu wykładniczego, aby zapisać liczbę? Czy to możliwe, że ten problem zostanie rozwiązany za pomocą kodowania binarnego, ale dla mnie brzmi to niekonsekwentnie.
Antonio Valerio Miceli-Barone
2
@ Miceli-Barone, To, co mówisz, miałoby zastosowanie do praktycznie każdego algorytmu wielopoziomowego, który generuje liczbę. Sam wyznacznik byłby raczej duży w najgorszym przypadku jednostronnie.
Raphael
@ Rafael: ok, widzę, że wartość bezwzględna wyznacznika macierzy (0,1) jest ograniczona przez(n+1)n+122n
Antonio Valerio Miceli-Barone
11

W ramach Holanta istnieje kilka przypadków, które są podatne na leczenie (z innych niż trywialne) powodów innych niż poprzez matchgates na płaskich wykresach.

1) Bramy Fibonacciego

2) Dowolny zestaw podpisów afinicznych .

3) Nie-ważone #CSP

...żeby wymienić tylko kilka.

Ponadto, twierdzenie BEST podaje algorytm wielomianowy do zliczania liczby obwodów Eulera na wykresie ukierunkowanym, chociaż część algorytmu wykorzystuje obliczanie determinant.

Tyson Williams
źródło