Komplexitätsklassen für die Auflistung aller Lösungen?

Bei Stack Overflow las ich eine Frage, ob es NP- schwierig sei, alle einfachen Zyklen in einem Diagramm mit einem bestimmten Knoten aufzulisten, und mir fiel ein, dass ich mir keine Komplexitätsklasse vorstellen konnte, für die dies gut geeignet war Sprechen Sie über Probleme der Form "Listen Sie alle Lösungen für dieses Problem." Die Klasse NP besteht in gewisser Weise aus Problemen, bei denen gefragt wird, ob mindestens eine Lösung vorhanden ist, die Klasse FNP nach einer einzelnen Lösung fragt und die Klasse #P nach der Anzahl der vorhandenen Lösungen, wobei sich keine dieser Fragen mit der Komplexität befasst alle möglichen Lösungen erschöpfend aufzuzählen.

Gibt es eine Komplexitätsklasse für die Beschreibung von Problemen, die die Form "haben, wenn ein Polynom-Zeit-berechenbares Prädikat und eine Zeichenkette , und alle für die wahr ist, vorbehaltlich [einige einfügen angemessene Komplexitätsbeschränkungen]? " Ich verstehe, dass es schwierig sein kann, die Einschränkungen festzulegen, da die Anzahl der Lösungen möglicherweise exponentiell größer ist als die Größe des Eingangs , obwohl dies nicht unüberwindbar erscheint. $P(x, y)$ $x$ $y$ $P(x, y)$ $x$

complexity-theory reference-request complexity-classes enumeration templatetypedef
quelle

Interessant. Vielleicht haben in der Praxis zu viele Fälle relevanter Probleme oft eine exponentielle Anzahl von Lösungen, wenn überhaupt. Instanzen für SAT und CLIQUE haben im Allgemeinen einen großen Lösungsraum.

Chi

Hier ist ein weiterer Ansatz, um dies zu formalisieren. Ein Problem

liegt in

(für X-enumerable) vor, wenn es einen X-Algorithmus

mit gibt, so dass

die

te Lösung (dh das

zurückgibt

P

$P$

X E

$XE$

A

$A$

A (x, i)

$A(x,i)$

i

$i$

I

$I$

y

$y$ mit

) wrt zurückgibt etwas bestellen. Man beachte, wie ähnlich man RE manchmal definiert. Dies umgeht die Größe des Lösungsraums und konzentriert sich darauf, wie schwierig es ist, die nächste Lösung zu finden. Die Gesamtkosten sind natürlich summiert.

P (x, y)

$P(x,y)$

Raphael

(Ich habe es noch nie als Klasse definiert gesehen , aber kennen Sie das Konzept der Aufzählung mit Polynomverzögerung ?)

@Raphael Dies ist möglicherweise nicht das, wonach wir suchen. Wenn zum Beispiel der beste Algorithmus für

alle Lösungen durchlaufen muss, bis er

gefunden hat und in der Zeit

abläuft , dann ist die gesuchte Komplexität

, aber Summation würde Komplexität

vorschlagen .

A (x, i)

$A(x,i)$

i

$i$

Θ (f (| x |))

$\Theta(f(|x|))$

Θ (f (| x |))

$\Theta(f(|x|))$

Θ (f (| x |)^{2})

$\Theta(f(|x|)^2)$

Lieuwe Vinkhuijzen

@RickyDemer Das ist es, was ich aus meinen Sleaves gezittert habe, nicht wahr? Gut zu wissen, dass es eine etablierte Formalisierung gibt.

Raphael

Das Konzept, nach dem Sie suchen, wird als Aufzählungskomplexität bezeichnet. Dabei handelt es sich um die Untersuchung der rechnerischen Komplexität, mit der alle Lösungen für ein Problem (oder die Mitglieder einer Sprache / Gruppe) aufgelistet werden. Aufzählungsalgorithmen können als zweistufiger Prozess modelliert werden: ein Vorberechnungsschritt und eine Aufzählungsphase mit Verzögerung . Beide Schritte haben ihre eigene zeitliche und räumliche Komplexität (möglicherweise auch Entropie). Im allgemeinen Sinn der Komplexität gibt es häufig Kompromisse zwischen diesen, die berücksichtigt werden müssen.

Der Vorberechnungsschritt führt einige Arbeiten aus, die erforderlich sind, bevor die erste Lösung aufgelistet wird. Dies kann das Auffinden der Lösung selbst oder das Initialisieren einer großen Datenstruktur umfassen, die die Gesamtverzögerung zwischen den einzelnen Lösungen verringert.

Die Verzögerung sind die Ressourcenkosten, die mit der zwischen beliebigen Aufzählungslösungen erforderlichen Berechnung verbunden sind. Mit anderen Worten ist die Verzögerung ein Maß für den Raum und die Zeit, die benötigt werden, um die Lösung nach der Lösung zu erzeugen . Probleme, deren Lösungen für jede Aufzählung Zeit benötigen, haben eine konstante Verzögerung. Eine Anforderung von $i+1^{th}$ $i^{th}$ $O(1)$ Zeit gesagt wird Polynom Verzögerung haben. $O(poly(n))$

Für das Aufzählungsproblem, das Sie in Ihrer Frage speziell erwähnt haben, sollten Sie in Abschnitt 2.1 von "Aufzählung: Algorithmen und Komplexität" von Johannes Schmidt (unten verlinkt) einen Blick auf die Klasse und ihre verwandten Geschwister werfen . $ENUM_{NP}$

Warum kümmern wir uns um Vorberechnungszeit und Verzögerung?

Verzögerung ist sehr wichtig, um die wahren Feinheiten von Aufzählungsproblemen zu verstehen. Auflisten der Elemente (bis zur Größe ) und , wo $\Sigma^*$ $n$ $\{ \vec{x} : \phi(\vec{x}) \}$ $\phi(\vec{x})$ ist eine Boolesche Formel (dh SAT) sowohl exponentielle Zeit. Allerdings Aufzählen durch $\Sigma*$ erfordert nur eine konstante Verzögerung, da Sie die Elemente einfach in einer bestimmten Reihenfolge durchgehen können. Nach allem, was wir wissen, kann die Verzögerung beim Auflisten von Lösungen für eine 3SAT-Instanz exponentiell sein. Unsere Aufgabe als Komplexitätstheoretiker ist es, herauszufinden, warum das letztere Problem grundlegend schwieriger (komplexer) ist als das erstere. Delay macht einen ziemlich guten Job darin, diesen Unterschied zu demonstrieren.

Ebenso müssen wir wissen, wie viel Vorberechnung durchgeführt wird. Wir können die Verzögerung für jedes Aufzählungsproblem auf konstante Zeit und Raum reduzieren, indem wir alle Lösungen vorberechnen und in einer Liste speichern, die zu einem späteren Zeitpunkt aufgelistet wird. Die Herausforderung besteht darin, das beste Gleichgewicht zwischen den beiden Ressourcen zu finden.

Die Reihenfolge, in der Sie die Elemente auflisten, kann auch die Komplexität beeinflussen. Wenn Ergebnisse in einer bestimmten sortierten Reihenfolge zurückgegeben werden sollen, müssen wir möglicherweise in beiden Schritten zusätzliche Berechnungen durchführen. Es werden jedoch auch Situationen untersucht, in denen eine beliebige Reihenfolge ausreicht (sofern jedes aufgezählte Element eindeutig ist).

$P$ $NP$

Ressourcen

Diese Umfrage (eigentlich ein Versuch der Formalisierung) soll Ihnen den Einstieg erleichtern. Es beweist auch einige grundlegende Hierarchiesätze.

Aufzählung: Algorithmen und Komplexität (Johannes Schmidt, 2009)

https://www.thi.uni-hannover.de/fileadmin/forschung/arbeiten/schmidt-da.pdf

Eine Aufzählung der Ergebnisse in Bezug auf die Komplexität der Aufzählung finden Sie in dieser Zusammenstellung, die von Kunihiro Wasa zusammengestellt wurde. Da es nach Problemtypen kategorisiert ist, finden Sie leicht eine Reihe von Artikeln, die sich mit der Aufzählung von Diagrammzyklen befassen. Es sollte einfach sein, die beteiligten Algorithmen so zu ändern, dass nur Zyklen mit einem bestimmten Knoten berücksichtigt werden.

http://www-ikn.ist.hokudai.ac.jp/~wasa/enumeration_complexity.html

mdxn
quelle

Σ^{*}

$\Sigma^*$

n

$n$

O (1)

$O(1)$

O (1)

$O(1)$

@j_random_hacker Ich glaube nicht, dass Ihr Denken falsch ist, obwohl die eigentliche Antwort auf Ihre Frage "es kommt darauf an". Die Autoren dieser Artikel geben in der Regel an, welches Berechnungsmodell (normales Tape TM vs. RAM vs. Word RAM) sie verwenden. Diese Auswahl ändert, was als Vorgang mit konstanter Zeit betrachtet werden kann und was nicht (z. B. Inkrementieren einer Zahl oder Generieren einer Ausgabe). Es wird davon ausgegangen, dass dieser Unterschied verschwindet, sobald Ihre Verzögerung aufgrund der erweiterten These von Church Turing polynomial wird.

mdxn

Komplexitätsklassen für die Auflistung aller Lösungen?

Antworten: