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

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?

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

Antworten:

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 v f . Das überrascht aber nicht. Einfach zu bestimmen, ob v f von v 0 erreichbar ist, ist in NL und somit in DET . Ich habe keine Ahnung von der Zählversion.v0vfvfv0

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{0,1}Xf(X)=1Uf|X|0|X|f(X)|1UfHn|0|0

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
(n+1)n+122n
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