Hat ein algorithmisches Problem eine zeitliche Komplexität, die vom Zählen dominiert wird?

Was ich als Zählen bezeichne, ist das Problem, das darin besteht, die Anzahl der Lösungen für eine Funktion zu finden. Genauer gesagt, bei gegebener Funktion $f:N\to \{0,1\}$ (nicht unbedingt Blackbox), approximieren Sie $\#\{x\in N\mid f(x)= 1\}= |f^{-1}(1)|$.

Ich suche nach algorithmischen Problemen, die eine Art Zählen beinhalten und bei denen die zeitliche Komplexität stark von diesem zugrundeliegenden Zählproblem beeinflusst wird.

Natürlich bin ich auf der Suche nach Problemen, die Probleme selbst nicht zählen. Und es wäre sehr dankbar, wenn Sie Dokumentation für diese Probleme bereitstellen könnten.

Dies ist eine Fortsetzung von Sureshs Antwort. Wie er sagt, gibt es in der Berechnungsgeometrie viele Konstruktionsprobleme, bei denen die Komplexität der Ausgabe eine unbedeutende Untergrenze für die Laufzeit eines Algorithmus darstellt. Zum Beispiel: Planare Linienanordnungen, 3-dimensionale Voronoi-Diagramme und planare Sichtbarkeitsgraphen haben im schlimmsten Fall eine kombinatorische Komplexität Daher benötigt jeder Algorithmus, der diese Objekte trivial konstruiert, Ω ( n 2 ) Zeit in der schlimmsten Fall. ( Für alle drei dieser Probleme gibt es O ( n 2 ) -Zeitalgorithmen.)$\Theta(n^2)$$\Omega(n^2)$$O(n^2)$

Es wird jedoch vermutet, dass ähnliche Einschränkungen auch für Entscheidungsprobleme gelten . Wie einfach können Sie zum Beispiel bei einer Menge von n Linien in der Ebene überprüfen, ob drei Linien durch einen gemeinsamen Punkt verlaufen? Nun, Sie könnten die Anordnung der Linien erstellen (das ebene Diagramm, das durch ihre Schnittpunkte und die Segmente zwischen ihnen definiert ist), aber das braucht $\Theta(n^2)$ Zeit. Eines der Hauptergebnisse meiner Doktorarbeit war, dass innerhalb eines eingeschränkten, aber natürlichen Entscheidungsbaummodells der Berechnung $\Omega(n^2)$ -Zeit erforderlich ist , um Dreifachschnittpunkte zu erkennen. Intuitiv, wir müssen alle aufzählen$\binom{n}{2}$ Schnittpunkte und suche nach Duplikaten.

In ähnlicher Weise gibt es eine Menge von Zahlen, bei denen sich Dreifache der Elemente zu Null summieren. Daher wird jeder Algorithmus (modelliert durch eine bestimmte Klasse von Entscheidungsbäumen) zu testen , ob ein gegebener Satz enthält drei Elemente , die Summe auf Null erfordert Zeit . (Es ist möglich, einige Protokolle über Parallelität auf Bitebene zu entfernen , aber wie auch immer.)$\Theta(n^2)$$\Omega(n^2)$

Ein weiteres Beispiel, ebenfalls aus meiner These, ist das Hopcroft-Problem: Enthält ein Punkt bei Punkten und Linien in der Ebene eine beliebige Linie? Es ist bekannt, dass die ungünstigste Anzahl von Punktlinieninzidenzen . Ich habe bewiesen, dass in einem eingeschränkten (aber immer noch natürlichen) Berechnungsmodell die Zeit erforderlich ist, um festzustellen, ob es überhaupt eine Punktlinieninzidenz gibt. Intuitiv müssen wir alle nahen Zufälle auflisten und jeden einzelnen prüfen, um festzustellen, ob es sich wirklich um einen Vorfall handelt.n Θ ( n 4 / 3 ) Ω ( n 4 / 3 )$n$$n$$\Theta(n^{4/3})$$\Omega(n^{4/3})$$\Theta(n^{4/3})$

Formal handelt es sich bei diesen Untergrenzen nur um Vermutungen, da sie eingeschränkte Rechenmodelle erfordern, die auf das jeweilige Problem, insbesondere auf das Hopcroft-Problem, spezialisiert sind. Der Nachweis der unteren Schranken für diese Probleme im RAM-Modell ist jedoch wahrscheinlich genauso schwierig wie jedes andere Problem der unteren Schranken (dh wir haben keine Ahnung) - siehe das SODA 2010-Papier von Patrascu und Williams, in dem Verallgemeinerungen von 3SUM mit der Exponentialzeit in Beziehung gesetzt werden Hypothese.

$|V|^{2.376}$ Verwendung des Coppersmith-Winograd-Matrixmultiplikationsalgorithmus ) und wurde erstmals 1978 von Itai und Rodeh bemerkt . Ebenso besteht der beste Weg, eine k-Clique zu erkennen, darin, die Anzahl von k zu ermitteln -cliques, wiederum über Matrixmultiplikation.

Valiant hat bewiesen, dass das Problem, die bleibende Karte einer Matrix zu finden, für #P vollständig ist . Siehe die Wikipedia-Seite zu diesem Thema. #P ist die Komplexitätsklasse, die dem Zählen der Anzahl der Akzeptanzpfade einer NP-Maschine entspricht.

Bipartite Planar (und log genus) Perfect Matching ist ein Problem, bei dem Kastelyns Algorithmus zum Zählen planarer Übereinstimmungen (erweitert um Galluccio und Loebl und parallelisiert durch Kulkarni, Mahajan und Vardarajan) auch in der Suchversion des Problems eine wichtige Rolle spielt. Alle relevanten Referenzen finden Sie in folgendem Artikel:

Einige perfekte Übereinstimmungen und perfekte halbintegrale Übereinstimmungen in NC. Raghav Kulkarni, Meena Mahajan und Kasturi R. Varadarajan. Chicago Journal of Theoretical Computer Science, Band 2008 Artikel 4.

Ich nehme "stark beeinflusst" eher als weiche Einschränkung als als Reduzierung. In diesem Sinne haben VIELE Probleme in der Berechnungsgeometrie Laufzeiten, die durch eine kombinatorische Struktur begrenzt sind. Beispielsweise hängt die Komplexität der Berechnung einer Anordnung von Formen direkt mit der eigentlichen Komplexität solcher Anordnungen zusammen.

Ein weiteres aktuelles Beispiel hierfür ist, dass verschiedene Probleme bei der Punktmusteranpassung zu Laufzeiten führen, die sich auf die Schätzung von Größen wie die Anzahl der wiederholten Abstände in einer Punktmenge usw. beschränken.

Sie sind sich nicht sicher, ob Sie danach gesucht haben, aber Phasenübergänge von NP-Complete-Problemen beruhen in hohem Maße auf probabilistischen Argumenten, die nur eine andere Form der Zählung darstellen.

LLL wurde verwendet, um einige Subset-Summen-Probleme mit geringer Dichte zu lösen, deren Erfolg auf Kurzgittervektoren mit hoher Wahrscheinlichkeit beruht, die die Kriterien einer Subset-Summen-Lösung erfüllen. Die Umfrageausbreitung stützt sich auf die Struktur des Lösungsraums (und die Anzahl der Lösungen bei der Festlegung von Variablen), um Lösungen in der Nähe des kritischen Schwellenwerts zu finden.

Borgs, Chayes und Pittel haben den Phasenübergang des (einheitlichen) Zufallszahlen-Partitionsproblems so gut wie vollständig charakterisiert und damit charakterisiert, wie viele Lösungen man für eine gegebene (zufällige) Instanz des Zahlen-Partitionsproblems erwarten kann.