Wie schwierig ist es, die Anzahl der einfachen Pfade zwischen zwei Knoten in einem gerichteten Diagramm zu zählen?

Question

Es gibt einen einfachen Polynomalgorithmus, um zu entscheiden, ob es einen Pfad zwischen zwei Knoten in einem gerichteten Diagramm gibt (machen Sie einfach einen Routine-Diagramm durch, beispielsweise mit beispielsweise Tiefen-First-Suchfest).

Es scheint jedoch, dass das Problem überraschenderweise viel schwieriger wird, wenn sie anstatt auf die Existenz zu testen, die wir wollen wollen zählen die Anzahl der Pfade.

Wenn wir Pfade erlauben, Eckpunkte wiederzuverwenden s zu t mit n Kanten. Wenn wir jedoch nur einfache Wege zulassen, die keine Eckpunkte wiederverwenden, ist die einzige Lösung, die ich mir vorstellen kann, die Brute -Force -Aufzählung der Pfade, etwas, das exponentielle Zeitkomplexität hat.

Deshalb frage ich,

• Ist die Anzahl der einfachen Pfade zwischen zwei Eckpunkten schwierig?
• Wenn ja, ist es eine Art NP-Vervollständigung? (Ich sage irgendwie, weil es technisch gesehen kein Entscheidungsproblem ist ...)
• Gibt es auch andere Probleme in P, die auch solche schwer zählenden Versionen haben? **

Answer 1

Die häufigste Komplexitätsklasse, die mit dem Zählen von Problemen verbunden ist, ist #P. Die Entscheidung, ob es einen einfachen Weg von einem bestimmten Knoten zu einem anderen gibt, ist eindeutig in NP. Das Zählen ist dann in #P.

Über die NP-Vervollständigung: Auch wenn dies kein Entscheidungsproblem ist, würde es kaum in NP passen: Es kann möglicherweise sein $ n! $ Wege und der Nichtdeterminismus hilft Ihnen nicht dabei (Sie müssen sie noch alle überprüfen)

Die Antwort auf Ihre beiden ersten beiden Frage lautet: Ja, es ist schwer, Es ist #P-Complete (Ref).

Die Wikipedia Artikel gibt relevante Fakten: 1) probabilistische Algorithmen sind nützlich, um #P-Complete-Funktionen zu approximieren, und das ist die Art von Algorithmus, die für die Näherung im vorherigen Artikel verwendet wird. 2) Es gibt andere einfache Probleme mit harten (#P-Completen-) Zählversionen:

• Finden (linear) im Vergleich zum Zählen aller Aufträge, die a erfüllen a DNF -Formel oder eine Instanz von 2-sa
• Finden (linear) vs. topologische Sendungen zählen
• Finding (O (ve)) gegen das Zählen perfekter Übereinstimmung in zweiparteilen Grafiken

Sie wissen bereits, dass, wenn Sie die Einschränkung "einfacher Pfad" entfernen, das Problem in P fällt (na ja, Sie müssen die Länge der Pfade durch ein Polynom der Größe des Diagramms gebunden oder die gebundene in Unary angeben)