Komplexe Analyse in der theoretischen Informatik

24

Es gibt viele Anwendungen der realen Analyse in der theoretischen Informatik, die Eigenschaftsprüfung, Kommunikationskomplexität, PAC-Lernen und viele andere Forschungsbereiche abdecken. Ich kann mir jedoch kein Ergebnis in TCS vorstellen, das auf einer komplexen Analyse beruht (außerhalb des Quantencomputers, wo komplexe Zahlen im Modell eine Rolle spielen). Hat jemand ein Beispiel für ein klassisches TCS-Ergebnis, das komplexe Analysen verwendet?

soft-question big-picture
quelle

1

Gute Frage! Ich würde vorschlagen, dass es besser ist, Ergebnisse im Zusammenhang mit der Zahlentheorie - z. B. die Verwendung der Riemann-Hypothese - auszuschließen, als das Quantencomputing, bei dem es sich meines Wissens eher um endlich dimensionale Systeme handelt.

Colin McQuillan

11

Wir verwenden komplexe Analysen in einem Papier „Der Grothen Konstante ist streng kleiner als Krivines Bound“ , die (von TCS - Sicht) eine Annäherung Algorithmus für das Problem gibt der Maximierung unterliegen . Siehe ttic.uchicago.edu/~yury/papers/grothendieck-krivine.pdf

\sum_{i, j} a_{i j} x_{i} y_{j}

$\sum_{i,j} a_{ij} x_i y_j$

x_{i}, y_{j} \in {\pm 1}

$x_i, y_j\in \{\pm 1\}$

Yury

3

@Yury das könnte sehr gut eine Antwort sein.

Suresh Venkat

14

Barvinoks komplexbasierter Algorithmus zur Approximation der permanenten Polynomialzeit-Algorithmen zur Approximation von permanenten und gemischten Diskriminanten innerhalb eines einfach exponentiellen Faktors .

Offensichtlich sind auch komplexe Operatoren (und einige komplexe Analysen) für das Quantencomputing wichtig.

Lassen Sie mich auch dieses Buch weiterempfehlen: Topics in Performance Analysis von Eitan Bachmat mit vielen tollen relevanten Themen und vielem mehr.

Gil Kalai
quelle

Das ist ein großartiges Beispiel, mir war dieses Ergebnis nicht bekannt - danke!

25

Es ist kein einzelnes Problem, aber das gesamte Gebiet der analytischen Kombinatorik (siehe das Buch von Flajolet und Sedgewick ) untersucht, wie die kombinatorische Komplexität der ~~Zählung von~~ Strukturen (oder sogar der Laufzeit von Algorithmen) analysiert werden kann, indem eine geeignete Erzeugungsfunktion notiert und die Struktur analysiert wird der komplexen Lösungen.

Suresh Venkat
quelle

Hallo Suresh, was meinst du mit 'die Komplexität analysieren'?

Andy Drucker

2

Ah, ich habe falsch geschrieben. Ich meinte "die kombinatorische Komplexität von Strukturen analysieren" - beheben.

Suresh Venkat

15

Jon Kelner wurde 2004 mit dem STOC Best Student Paper Award für seine Arbeit "Spektrale Partitionierung, Eigenwertgrenzen und Kreispackungen für Graphen beschränkter Gattungen" ausgezeichnet.

Ich zitiere nur aus dem Abstract:

Als unser wichtigstes technisches Lemma beweisen wir ein O (g / n), das an den zweitkleinsten Eigenwert des Laplace-Graphen gebunden ist, und zeigen, dass dieser eng ist, wodurch eine Vermutung von Spielman und Teng aufgelöst wird. Während dieses Lemma im Wesentlichen kombinatorischer Natur ist, kommt sein Beweis aus der kontinuierlichen Mathematik, die sich auf die Theorie der Kreispackungen und die Geometrie kompakter Riemann-Oberflächen stützt.

Die Verwendung komplexer Analysen (und anderer "kontinuierlicher" mathematischer Methoden), um "traditionelle" Graphentrennungsprobleme anzugehen, war einprägsam und ist der Hauptgrund, warum dieses Papier in meinem Kopf steckte, obwohl es absolut nichts mit meiner Forschung zu tun hat.

Mugizi Rwebangira
quelle

8

Ich vermute, Sie interessieren sich mehr für komplexe Analysen, die direkt im Proof verwendet werden. Hier sind jedoch zwei Beispiele aus einem Algorithmuskurs auf Hochschulniveau, an dem ich gerade teilnehme:

a) Schnelle Fouriertransformation, zum Beispiel bei der Polynommultiplikation. Obwohl die Implementierung mit Modulo-Arithmetik oder Gleitkomma (und einigen arithmetischen Analysen) erfolgen kann, lässt sich der Beweis am besten anhand komplexer Zahlen und ihrer Einheitswurzeln verstehen. Ich habe mich nicht mit dem Thema befasst, bin mir aber bewusst, dass FFT eine breite Palette von Anwendungen hat.

b) Wenn man das RAM-Modell generell mit der Fähigkeit ausstattet, komplexe Zahlen in konstanter Zeit zu verarbeiten (Real- und Imaginärteil haben immer noch eine endliche Genauigkeit), kann man Probleme geschickt codieren und Eigenschaften der komplexen Zahlen ausnutzen, die eine Lösung aufzeigen könnten (siehe auch die Kommentare, warum dies nicht zulässt, dass Sie schneller sind).

Chazisop
quelle

Haben Sie ein Beispiel für die zweite Beobachtung? Es ist trivial, eine "komplexe O (log n) -Bit-Ganzzahl" -Klasse zu dem Standard-RAM mit Operationen mit konstanter Zeit hinzuzufügen. Oder mit "schneller" meinen Sie "um den Faktor 2 schneller"?

Jeffs

Dies war eine Übung aus der Vorlesung: "Angenommen, Sie haben es mit einem erweiterten RAM zu tun, der mit komplexen Zahlen zu Stückkosten pro Multiplikation, Division, Addition und Subtraktion rechnen kann. Außerdem kann er den Absolutwert | c | von a berechnen komplexe Zahl c in Zeiteinheiten. Außerdem "kennt" sie die komplexen Konstanten 0, 1 und i. Zeigen Sie, dass bei einer positiven ganzen Zahl n in einem solchen erweiterten RAM die Zahl n! in berechnet werden kann. Zeit. Die Lösung verwendet die Polynom-Multiplikation,

O (\sqrt{n} \log^{2} n)

$O( \sqrt{n} \log ^{2} n)$

soweit

6

Der vorgeschlagene Algorithmus erfordert eine zeitkonstante reelle Arithmetik mit unendlicher Genauigkeit. (Sie können eine -Bit-Ganzzahl nicht in -Zeit berechnen, wenn Sie eine Maschine mit -Bit-Wörtern verwenden, da Sie nicht einmal Zeit hätten, die aufzuschreiben Ausgabe!) Die Frage ist, ob Sie dem realen RAM-Modell Quadratwurzeln hinzufügen sollen , nicht komplexe Zahlen an sich.

Ω (n \log n)

$\Omega(n\log n)$

o (n)

$o(n)$

O (\log n)

$O(\log n)$

Jeffs

Vielen Dank für den Kommentar, es ist sehr aufschlussreich. Ich denke, ich sollte meine Antwort dahingehend aktualisieren, dass nur ein Problem mit komplexen Zahlen geschickt codiert wird, dh eine Lösung zu finden, die Sie sonst verpassen würden.

Chazisop

6

Vielleicht liegt diese Anwendung etwas zwischen TCS und Disc-Mathematik, aber ich war etwas überrascht, als ich den Artikel "Über die gebogenen Booleschen Funktionen, die symmetrisch sind" von Petr Savicky (http://www2.cs.cas.cz/~savicky/) las. papers / symmetric.ps). Die Theoreme beziehen sich nur auf Boolesche Funktionen, jedoch verwendet einer der Beweise komplexe Zahlen.

Magnus Find
quelle

5

In unserer Arbeit " Approximating Linear Threshold Predicates " verwenden wir Cauchys Residue Theorem aus der komplexen Analyse als das wichtigste technische Werkzeug .

MCH
quelle

5

Der Koebe-Andreev-Thurston-Kreispacksatz stammt aus dem Riemann-Mapping-Satz und hat verschiedene algorithmische Aspekte. Zum Beispiel ist dies ein Beweis des Lipton-Tarjan-Seperorsatzes für planare Graphen.

Gil Kalai
quelle

5

Frisch aus dem Ofen:

Ein polynomieller Zeitalgorithmus für die Wiederherstellung der Bevölkerung nach Verlust Von: Ankur Moitra, Michael Saks

Zitat aus dem Aufsatz: "Hier werden wir das im vorherigen Abschnitt angegebene Unsicherheitsprinzip unter Verwendung von Werkzeugen aus der komplexen Analyse beweisen. Einer der nützlichsten Sätze zum Verständnis der Wachstumsrate holomorpher Funktionen in der komplexen Ebene ist Hadamards Drei-Kreis-Theorem. .. "

Gil Kalai
quelle

Lassen Sie mich kurz skizzieren, wie der Drei-Kreise-Satz in dieser Arbeit verwendet wird. Um eine Quantität zu minimieren , die einige lineare Bedingungen erfüllt, betrachten sie das Duale dieser LP. Anzeigen der dualen Variablen als Koeffizienten eines Polynoms, das zu maximier äquivalent wird Gesamtgrad polys erfüllt wobei ist zusammengesetzt mit eine affine Transformation und bezeichnet die Summe der abs-Werte von Koeffizienten.

σ

$\sigma$

p (0) - ϵ ‖ p ‖_{1}

$p(0) - \epsilon \|p\|_1$

n

$n$

p

$p$

‖ q ‖_{1} \leq 1

$\|q\|_1 \leq 1$

q

$q$

p

$p$

‖ \cdot ‖_{1}

$\|\cdot\|_1$

Arnab

(Forts.) Nun ist die schöne Beobachtung, dass wobei die Einheitsscheibe in der komplexen Ebene von Radius 1 ist. Wenn wir dies verwenden Entspannung, das Problem läuft darauf hinaus, zu maximieren, , dass über einer kleineren Scheibe in durch begrenzt ist . Wenn wir eine Koordinatentransformation durchführen, befinden wir uns im Dreikreissatz: Eine holomorphe Funktion ist an Punkte in zwei konzentrischen Kreisen gebunden und begrenzt die Funktion auf jedem Kreis mit Zwischenradius.

‖ p ‖_{1} \geq ‖ p ‖_{s u p}^{D_{1}}

$\|p\|_1 \geq \|p\|_{sup}^{D_1}$

D_{1}

$D_1$

p (0) - ‖ p ‖_{s u p}^{D_{1}}

$p(0) - \|p\|_{sup}^{D_1}$

p

$p$

1

$1$

D_{1}

$D_1$

Arnab

(Forts.) Für das Problem bedeutet dies, dass wenn über einer kleineren Scheibe durch begrenzt ist in . (Dank eines wunderbaren Vortrags von Mike Saks, der das Papier erklärt.)

‖ p ‖_{s u p}^{D_{1}} \geq | p (0) |^{Ω (1)}

$\|p\|_{sup}^{D_1} \geq |p(0)|^{\Omega(1)}$

p

$p$

1

$1$

D_{1}

$D_1$

Arnab

5

In Abschnitt A.4 dieses Artikels verwenden wir eine komplexe Analyse, die uns zu einer Derandomisierung des Indyk-Algorithmus für die Schätzung in Datenströmen ( ) führt, die optimale bietet: $\ell_p$ $0 < p < 2$

Daniel M. Kane, Jelani Nelson und David P. Woodruff. Über die exakte räumliche Komplexität des Skizzierens und Streamens kleiner Normen. SODA 2010.

Sie können damit fortfahren, einen Beweis zu schreiben, bei dem die komplexe Analyse nicht explizit erwähnt wird (siehe den ersten Aufzählungspunkt im Abschnitt "Notizen" für dieses Papier auf meiner Webseite), aber selbst bei diesem Beweis lauert eine komplexe Analyse unter der Decke.

Jelani Nelson
quelle

4

In einem kürzlich erschienenen Aufsatz von Naor, Regev und Vidick werden komplexe Zahlen und Analysen verwendet, die zu Näherungsalgorithmen für NP-harte Optimierungsprobleme führen: http://arxiv.org/abs/1210.7656

Clement C.
quelle

Ein weiteres Papier, das sich zufälliger Wurzeln der Einheit bedient, sind Daniel M. Kane, Kurt Mehlhorn, Thomas Sauerwald und He Sun. Zählen beliebiger Untergraphen in Datenströmen. ICALP 2012.

Jelani Nelson

3

Kürzlich gab Vishnoi einen Algorithmus an, der TSP-Touren mit einer Länge von höchstens in regulären einfachen Diagrammen findet ( talk & blog ). Die Analyse verwendet entscheidend die Van-der-Waerden-Vermutung (auch bekannt als Egorychev-Falikman-Theorem): Die Permanenz jeder doppelt stochastischen Matrix ist mindestens . Die Beweise von Egorychev und Falikman führten zu tiefen Ergebnissen in der konvexen Geometrie (insbesondere der Alexandrov-Fenchel-Ungleichung). Andererseits verwendet ein neuer Beweis von Gurvits nur die elementare Komplexanalyse und ist ein Juwel (nette Darstellung) $n + O(n/\sqrt{k})$ $k$ $n \times n$ $n!/n^n$ von Laurent und Schrijver im MAA Monthly). Das Verlassen der realen Linie für das komplexe Flugzeug scheint für Gurvits 'Beweis wesentlich zu sein und vereinfacht die Sache erheblich.

Sasho Nikolov
quelle

0

Es gibt einige Untersuchungen, die Unentscheidbarkeit im Zusammenhang mit verschiedenen Aspekten der Berechnung der Mandelbrot-Menge zeigen , einem berühmten Prototyp- Fraktal, das unter Verwendung komplexer Zahlen berechnet wird und die Anzahl der Iterationen zählt, die mit der Gleichung , um ein unbegrenztes zu erzielen aufsteigende Reihenfolge. Ein detaillierter Bericht und eine Umfrage sind in [1] zu finden, die in einem Physikjournal erschienen sind, jedoch unter starker Verwendung von TCS-Konzepten, z. $z \leftarrow z^2 + c$

[1] Unzugänglichkeit und Unentscheidbarkeit in Berechnungs-, Geometrie- und dynamischen Systemen Asaki Saito, Kunihiko Kaneko

[2] Eine Theorie der Berechnung und Komplexität über die reellen Zahlen Lenore Blum, 1990

vzn
quelle

0

Nister, Hartley und Stewenius verwendeten die Galois-Theorie, um die Optimalität bestimmter Algorithmen in der Bildverarbeitung zu beweisen. Obwohl es sich nicht speziell um eine Instanz von Complex Analysis handelt, ist diese Arbeit aufgrund des grundlegenden Satzes der Algebra eng mit . $\mathbb{C}$

Reb.Cabin
quelle

Komplexe Analyse in der theoretischen Informatik

Antworten: