Komplexität beim Zählen von Pfaden in einem Diagramm

12

Bei einem gerichteten Graphen mit n Knoten, bei dem jeder Scheitelpunkt genau zwei ausgehende Kanten hat, und einer natürlichen Zahl N, die binär codiert ist, zwei Scheitelpunkte s und t,

Ich möchte die Anzahl der (nicht unbedingt einfachen) Pfade von s bis t innerhalb von N Schritten zählen.

Ist das ein # P-hartes Problem? Oder allgemein, wie komplex ist dieses Problem?

maomao
quelle
6
Haben Sie versucht, die Matrix mit Strom zu versorgen?
Yuval Filmus
1
ja, aber die komplexität ist meines erachtens noch nicht bekannt.
Maomao
Muss die Wanderung um t enden oder muss sie nur irgendwann auf der Wanderung besucht werden?
Tyson Williams
es muss bei t enden.
Maomao
1
@Geekster Für den vollständigen Digraphen auf 3 Eckpunkten mit ist die Zählung die N-te Fibonacci-Zahl, deren Größe in N exponentiell ist, so wie David in seiner Antwort für jedes Diagramm argumentiert hat. st
Tyson Williams

Antworten:

13

Die ausgegebene Anzahl von Pfaden kann (wählen Sie s willkürlich und wählen Sie dann t als den Scheitelpunkt, der der Endpunkt der größten Anzahl von 2 N Schritten von s ist ), der Ω ( N ) erfordert.Ω(2N/n)st2NsΩ(N)Bits zum expliziten Aufschreiben; Dies ist in der Eingabegröße exponentiell. Andererseits weist der Matrix-Potenzierungsansatz ein Komplexitätspolynom in der Summe der Eingabe- und Ausgabegrößen auf. Das scheint es also genau in die Klasse der Zählprobleme zu ordnen, die eine Ausgabe in Exponentialgröße haben und in ihrer Ausgabegröße deterministisch in Zeitpolynomen gelöst werden können definitiv nicht #EXP (analog zu NEXP).

David Eppstein
quelle
1
danke, aber ich möchte immer noch wissen, ob dieses problem hart ist. P
Maomao
1
Um die großen Zahlen in Davids iteriertem Quadrierungsansatz zu vermeiden, können wir alle Berechnungen modulo einer Primzahl p durchführen. Dann läuft der Gesamtalgorithmus im Zeitpolynom in . Wenn das Problem unter polynomial-zeitlich sparsamen Viel-Eins-Reduktionen # P-schwer wäre, würde der Algorithmus mit p = 2 P = P implizieren , was wir nicht glauben. n+LogN+Logpp=2
Holger
@Holger gäbe es nicht ein ähnliches Argument für die Permanent? das heißt , wenn permanent # P-hard dann Perm 2 mod wäre P hart. Aber Perm mod 2 = Det mod 2, der in P.
SamiD
@SamiD: Genau, dein Argument zeigt, dass die bleibende Karte unter sparsamen Reduktionen wahrscheinlich nicht # P-hart ist . Die bekannten Beweise verwenden Turing-Reduktionen.
Holger
Ich stimme zu. Tut mir leid, ich hatte den sparsamen One- Part verpasst . Daher kann das Matrix-Powering-Powering-Problem unter Turing-Reduktionen durchaus # P-hart sein.
SamiD
4

Das Finden eines Bits von wobei A die Adjazenzmatrix des gegebenen Graphen ist, reduziert sich auf das Problem B i t S L P, das zuerst in [ABKPM] definiert wurde und dessen untere Grenze # P in demselben Papier festgelegt ist. Es ist jedoch offen, ob die Reduktion in der umgekehrten Richtung gilt, dh von B i t S L P bis zum Matrixversorgungsproblem.AN[s,t]EINBichtSLP#PBitSLP

Beachten Sie, dass genau innerhalb der Zählhierarchie C HP S P A C E liegt . Die bekannteste Obergrenze für dieses Problem, nämlich. P H P P P P P P ist von hier .BitSLPCHPSPACEPHPPPPPP

SamiD
quelle
1

Das Problem ist # P-vollständig. Betrachten Sie das Problem des Zählens der kürzesten Pfade in einem Diagramm (ND31 in Garey & Johnson), das für die Zählversion # P-vollständig ist. Lesen Sie den Kommentar sorgfältig durch. Dies gibt die Antwort für Wege der Länge . Um die Antwort für Pfade mit der Länge = N zu erhalten , rufen Sie das Problem der kürzesten Pfade für N und N - 1 auf und subtrahieren Sie letztere von ersteren, dh führen Sie eine subtraktive Reduktion durch.N=NNN1

Da die Reduzierung von #HAMILTONIAN PATHS / CIRCUITS auf #SHORTEST PATHS auch für 3-reguläre Diagramme funktioniert, funktioniert das Ergebnis der # P-Vollständigkeit auch für die Einschränkung von Digraphen mit einem Grad von .2

Miki Hermann
quelle
2
Das ursprüngliche Problem erfordert nicht, dass der Pfad einfach ist, daher denke ich nicht, dass die Antwort richtig ist.
Maomao
3
Wie kann es # P-vollständig sein, wenn alle #P-Probleme eine Anzahl von Lösungen haben, die in der Eingabegröße exponentiell sind und diese doppelt exponentiell ist?
David Eppstein
Was bedeutet "ND31" im Kontext von Gareys und Johsons Buch?
Tyson Williams