Überraschende Algorithmen zum Zählen von Problemen

54

Es gibt einige Zählprobleme, bei denen exponentiell viele Dinge gezählt werden (im Verhältnis zur Größe der Eingabe) und die dennoch überraschende, polynomzeitgenaue, deterministische Algorithmen aufweisen. Beispiele beinhalten:

Zählen perfekter Übereinstimmungen in einem planaren Graphen (dem FKT-Algorithmus ), der die Grundlage für die Funktionsweise holographischer Algorithmen bildet .
Spannbäume in einem Graphen zählen (über Kirchhoffs Matrixbaumsatz ).

Ein wichtiger Schritt in beiden Beispielen ist die Reduzierung des Zählproblems auf die Berechnung der Determinante einer bestimmten Matrix. Eine Determinante ist natürlich selbst eine Summe von exponentiell vielen Dingen, kann jedoch überraschenderweise in Polynomzeit berechnet werden.

Meine Frage ist: Gibt es irgendwelche "überraschend effizienten" exakten und deterministischen Algorithmen zum Zählen von Problemen, die sich nicht auf die Berechnung einer Determinante reduzieren lassen?

cc.complexity-theory counting-complexity big-picture Ashley Montanaro
quelle

8

Übrigens reduzieren sich viel mehr Zählprobleme auf die Berechnung der Determinante. Die Ganzzahldeterminante ist für die Klasse GapL vollständig, die #L enthält.

5501

11

Ich weiß nicht, ob die folgenden Probleme auf die Berechnung der Determinante zurückzuführen sind oder nicht, aber ich werde sie trotzdem auflisten:

1) Zählen der Anzahl von Pfaden in einer DAG von einem Knoten zu einem Knoten . Das überrascht aber nicht. Einfach zu bestimmen, ob von erreichbar ist, ist in NL und somit in DET . Ich habe keine Ahnung von der Zählversion. $v_0$ $v_f$ $v_f$ $v_0$

2) Zählen der Anzahl der in der MSO-Logik definierbaren Problemlösungen in Strukturen mit begrenzter Baumbreite. Siehe zum Beispiel das Papier, das Werke von Courcelle, Arnborg und anderen aufzeigt .

$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
quelle

Danke - Artikel (2) und (3) sind interessant, aber irgendwie nicht ganz das, wonach ich gesucht habe; Zählprobleme mit begrenzter Baumbreite scheinen eher Sonderfälle zu sein, in denen die Struktur, mit der Sie arbeiten, tatsächlich polynomiell begrenzt ist. Ich war mehr an Fällen interessiert, in denen "wirklich" exponentiell viele Objekte zu zählen sind, aber sie können irgendwie auf magische Weise in der Polynomzeit gezählt werden.

Ashley Montanaro

Würde das nicht bedeuten, dass der Algorithmus, wenn Sie eine unäre Codierung verwenden, exponentielle Zeit benötigt, nur um die Zahl zu schreiben? Ist es möglich, dass dieses Problem durch die Verwendung von Binärcodierung behoben wird, aber das klingt für mich uninteressant.

Antonio Valerio Miceli-Barone

2

@ Miceli-Barone, Was Sie sagen, würde für so ziemlich jeden Poly-Time-Algorithmus gelten, der eine Zahl ausgibt. Die Determinante selbst wäre im schlimmsten Fall unärgerlich ziemlich groß.

Raphael

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

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

11

Zählen der Anzahl von Gitterpunkten in einem rationalen Polytop (wenn die Dimension konstant ist) in der Polynomzeit aufgrund von Alexander Barvinok.

Yoshio Okamoto
quelle

2

Was ist die Haupttechnik?

Suresh Venkat

2

Eine kurze generierende Funktion. Der folgende Expository-Artikel würde uns weitere Ideen geben. arxiv.org/abs/math/0506466

Yoshio Okamoto

11

Im Holant-Framework gibt es mehrere Fälle, die (aus nicht trivialen) Gründen als über Matchgates in ebenen Diagrammen nachvollziehbar sind.

1) Fibonacci-Tore

2) Beliebige affine Signaturen .

3) Nicht negativ gewichtete #CSPs

...um ein paar zu nennen.

Das BEST-Theorem gibt auch einen polynomiellen Zeitalgorithmus zum Zählen der Anzahl von Eulerschaltungen in einem gerichteten Graphen an, obwohl ein Teil des Algorithmus eine Determinantenberechnung verwendet.

Tyson Williams
quelle

Überraschende Algorithmen zum Zählen von Problemen

Antworten: