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

Zliczanie idealnych dopasowań na wykresie planarnym ( algorytm FKT ), który jest podstawą działania algorytmów holograficznych .
Zliczanie drzew rozciągających się na wykresie (za pomocą twierdzenia Kirchhoffa o macierzy ).

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?

cc.complexity-theory counting-complexity big-picture 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

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. $v_0$ $v_f$ $v_f$ $v_0$

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}\rightarrow \{0,1\}$ $x$ $f(x)=1$ $U_f$ $|x\rangle|0\rangle$ $|x\rangle|f(x)\rangle$ $|1\rangle$ $U_fH^{\otimes n}|0\rangle|0\rangle$

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

\frac{(n + 1)^{\frac{n + 1}{2}}}{2^{n}}

$\frac{(n + 1)^{\frac{n+1}{2}}}{2^n}$

Antonio Valerio Miceli-Barone

11

Zliczanie liczby punktów sieci w racjonalnym polotopie (gdy wymiar jest stały) w czasie wielomianowym , ze względu na Aleksandra Barvinoka.

Yoshio Okamoto
źródło

2

jaka jest główna technika?

Suresh Venkat

2

Krótka funkcja generująca. Poniższy artykuł z expository dałby nam więcej pomysłów. arxiv.org/abs/math/0506466

Yoshio Okamoto

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

Zaskakujące algorytmy liczenia problemów

Odpowiedzi: