Kompleksowa analiza w informatyce teoretycznej

24

Istnieje wiele zastosowań rzeczywistych analiz w informatyce teoretycznej, obejmujących testowanie własności, złożoność komunikacji, uczenie się PAC i wiele innych dziedzin badań. Nie mogę jednak wymyślić żadnego wyniku w TCS, który opierałby się na złożonej analizie (poza obliczeniami kwantowymi, gdzie liczby zespolone są nieodłączne w modelu). Czy ktoś ma przykład klasycznego wyniku TCS wykorzystującego złożoną analizę?

soft-question big-picture
źródło

1

Świetne pytanie! Sugerowałbym, że lepiej byłoby wykluczyć wyniki związane z teorią liczb - np. Jakimkolwiek zastosowaniem hipotezy Riemanna - niż obliczenia kwantowe, które zwykle dotyczą systemów skończonych wymiarów (o ile mi wiadomo).

Colin McQuillan,

11

Używamy złożonych analiz w artykule „The Grothendieck Constant jest ściśle Mniejsza niż Krivine nic nie wiąże”, który (z punktu widzenia TCS) daje algorytm aproksymacji dla problemu maksymalizacji

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

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

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

$x_i, y_j\in \{\pm 1\}$ . Zobacz ttic.uchicago.edu/~yury/papers/grothendieck-krivine.pdf

Yury

3

@ Yury może to być odpowiedź.

Suresh Venkat

14

Kompleksowy algorytm Barvinoka do aproksymacji stałych algorytmów wielomianu czasowego w celu aproksymacji stałych i mieszanych dyskryminatorów w ramach prostego czynnika wykładniczego .

Oczywiście złożone operatory (i niektóre złożone analizy) są ważne w obliczeniach kwantowych.

Pozwól, że polecę także tę książkę: Tematy w analizie wydajności autorstwa Eitana Bachmata z wieloma świetnymi istotnymi zagadnieniami i innymi świetnymi rzeczami.

Gil Kalai
źródło

To świetny przykład, nie byłem świadomy tego wyniku - dzięki!

25

To nie jest pojedynczy problem, ale cała dziedzina kombinatoryki analitycznej (patrz książka Flajoleta i Sedgewicka ) bada, jak analizować kombinatoryczną złożoność struktur ~~zliczających~~ (lub nawet czasy działania algorytmu), zapisując odpowiednią funkcję generującą i analizując strukturę złożonych rozwiązań.

Suresh Venkat
źródło

Cześć Suresh, co rozumiesz przez „analizowanie złożoności”?

Andy Drucker

2

Ach, źle napisałem. Miałem na myśli „przeanalizuj kombinatoryczną złożoność struktur” - naprawię.

Suresh Venkat

15

Jon Kelner zdobył nagrodę STOC Best Student Paper Award w 2004 r. Za artykuł „Podział spektralny, granice wartości własnych i wypełnienia kół dla wykresów związanych rodzajów”

Przytoczę tylko streszczenie:

Jako nasz główny techniczny lemat, dowodzimy O (g / n) związaną z drugą najmniejszą wartością własną Laplaciana takich wykresów i pokazujemy, że jest to ścisłe, rozwiązując w ten sposób przypuszczenie Spielmana i Tenga. Chociaż ten lemat ma zasadniczo charakter kombinatoryczny, jego dowodem jest ciągła matematyka, czerpiąca z teorii upakowania okręgu i geometrii zwartych powierzchni Riemanna.

Zastosowanie złożonej analizy (i innej „ciągłej” matematyki) do ataku na „tradycyjne” problemy z separatorem grafów było niezapomniane i jest głównym powodem, dla którego ten papier utknął mi w głowie, mimo że jest całkowicie niezwiązany z moimi badaniami.

Mugizi Rwebangira
źródło

8

Wydaje mi się, że bardziej interesuje Cię złożona analiza stosowana bezpośrednio w dowodzie. Oto jednak dwa przykłady z klasy Algorytmy na poziomie magisterskim, w której obecnie uczęszczam:

a) Szybka transformata Fouriera, na przykład stosowana w mnożeniu wielomianowym. Chociaż implementacja może być wykonana za pomocą modulo arytmetycznej lub zmiennoprzecinkowej (i pewnej analizy arytmetycznej), dowód najlepiej zrozumieć w kategoriach liczb zespolonych i ich pierwiastków jedności. Nie zagłębiałem się w ten temat, ale mam świadomość, że FFT ma szeroki zakres zastosowań.

b) Ogólnie rzecz biorąc, wyposażenie modelu RAM w zdolność do obsługi liczb zespolonych w stałym czasie (rzeczywiste i urojone części wciąż mają skończoną precyzję) pozwala sprytnie kodować problemy i wykorzystywać właściwości liczb zespolonych, które mogą ujawnić rozwiązanie (patrz także komentarze, dlaczego to nie pozwoli ci być szybszym).

chazisop
źródło

Czy masz przykład drugiej obserwacji? To proste, aby dodać klasę „złożoną liczbę całkowitą O (log n)” do standardowej pamięci RAM za pomocą operacji o stałym czasie. Czy przez „szybsze”, masz na myśli „szybsze o współczynnik 2”?

Jeffε

Było to ćwiczenie z wykładu: „Załóżmy, że masz do czynienia z rozszerzoną pamięcią RAM, która może obliczać liczby zespolone przy koszcie jednostkowym pomnożenia, dzielenia, dodawania i odejmowania. Ponadto może również obliczać wartość bezwzględną | c | liczba zespolona cw jednostkowym czasie. Ponadto „zna” stałe zespolone 0, 1 i i. Pokaż, że biorąc pod uwagę dodatnią liczbę całkowitą n na tak rozszerzonej pamięci RAM, liczbę n! można obliczyć w

czas. Rozwiązanie wykorzystuje mnożenie wielomianowe, z tego co wiem jest szybsze niż standardowy model RAM.

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

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

chazisop

6

Zaproponowany algorytm wymaga rzeczywistej arytmetyki o nieskończonej precyzji. (Nie możesz obliczyć liczby całkowitej

-bit w czasie

za pomocą maszyny ze słowami

-bit, ponieważ nie miałbyś nawet czasu na zapisanie wyniku!) Pytanie polega na dodaniu pierwiastków kwadratowych do rzeczywistego modelu pamięci RAM, a nie samych liczb zespolonych .

Ω (n \log n)

$\Omega(n\log n)$

o (n)

$o(n)$

O (\log n)

$O(\log n)$

Jeffε

Dzięki za komentarz, jest bardzo pouczający. Myślę, że powinienem zaktualizować swoją odpowiedź tylko do sprytnego kodowania problemu ze złożonymi liczbami, tj. Aby znaleźć rozwiązanie, którego w innym przypadku byś nie zauważył.

chazisop

6

Być może ta aplikacja jest nieco między TCS a matematyką dyskową, ale byłem nieco zaskoczony, gdy przeczytałem artykuł „O wygiętych funkcjach logicznych, które są symetryczne” Petr Savicky (http://www2.cs.cas.cz/~savicky/ papers / symmetric.ps). Twierdzenia dotyczą tylko funkcji boolowskich, jednak jeden z dowodów wykorzystuje liczby zespolone.

Magnus Find
źródło

5

Używamy twierdzenia Cauchy'ego o złożonej analizie jako głównego narzędzia technicznego w naszym artykule „ Przybliżanie predykatów progów liniowych ”.

MCH
źródło

5

Twierdzenie o upakowaniu kół Koebe-Andreev-Thurston powstało w twierdzeniu Riemanna o odwzorowaniu i ma różne aspekty algorytmiczne. Na przykład, jest to dowód twierdzenia o separatorze Liptona-Tarjana dla grafów płaskich.

Gil Kalai
źródło

5

Świeżo z piekarnika:

Algorytm czasu wielomianowego do odzyskiwania utraconej populacji Autor: Ankur Moitra, Michael Saks

Cytując z pracy: „Udowodnimy tutaj zasadę nieokreśloności podaną w poprzednim rozdziale przy użyciu narzędzi z analizy złożonej. Być może jednym z najbardziej użytecznych twierdzeń w zrozumieniu tempa wzrostu funkcji holomorficznych w płaszczyźnie złożonej jest Twierdzenie Trzech Koła Hadamarda. .. ”

Gil Kalai
źródło

σ

$\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$ oznacza sumę wartości abs współczynników.

arnab

‖ 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$ . Dokonując transformacji współrzędnych, znajdujemy się w ustawieniu twierdzenia o Trzech Okręgach: funkcja holomorficzna jest ograniczona do punktów w dwóch koncentrycznych okręgach, ograniczając funkcję na dowolnym okręgu o średnim promieniu.

arnab

‖ 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$

5

$\ell_p$ $0 < p < 2$

Daniel M. Kane, Jelani Nelson, David P. Woodruff. Dokładna złożoność przestrzeni szkicowania i przesyłania strumieniowego małych norm. SODA 2010.

Możesz uciec od napisania dowodu, który nie wspomina wyraźnie o złożonej analizie (patrz pierwszy punkt w sekcji „uwagi” tego artykułu na mojej stronie), ale nawet ten dowód zawiera złożoną analizę czającą się pod przykryciem.

Jelani Nelson
źródło

4

W ostatnim artykule Naora, Regeva i Vidicka zastosowano liczby zespolone i analizy, które dają wyniki w algorytmach aproksymacyjnych dla problemów optymalizacji NP-trudnych: http://arxiv.org/abs/1210.7656

Klemens C.
źródło

Kolejny artykuł, który wykorzystuje losowe korzenie jedności, to Daniel M. Kane, Kurt Mehlhorn, Thomas Sauerwald i He Sun. Zliczanie dowolnych subgrafów w strumieniach danych. ICALP 2012.

Jelani Nelson

3

Niedawno Vishnoi podał algorytm, który określa długość tras TSP najwyżej $n + O(n/\sqrt{k})$ w $k$ -regularne proste wykresy ( dyskusja i blog ). Analiza zasadniczo wykorzystuje hipotezę van der Waerdena (zwaną także twierdzeniem Egorycheva-Falikmana): trwałą dowolność podwójnie stochastyczną $n \times n$ matryca jest co najmniej $n!/n^n$ . Dowody Egorycheva i Falikmana wykorzystały głębokie wyniki w geometrii wypukłej (w szczególności nierówności Aleksandrowa-Fenchela). Z drugiej strony, najnowszy dowód Gurvitsa wykorzystuje tylko elementarną złożoną analizę i jest dość klejnotem (ładna prezentacja Laurenta i Schrijvera w miesięczniku MAA). Pozostawienie prawdziwej linii dla złożonej płaszczyzny wydaje się niezbędne dla dowodu Gurvitsa i bardzo upraszcza sprawy.

Sasho Nikolov
źródło

0

istnieją badania wskazujące na nierozstrzygalność związaną z różnymi aspektami obliczeń zbioru Mandelbrota , słynnego, prototypowego fraktala, który jest obliczany przy użyciu liczb zespolonych i zliczania liczby iteracji związanych z równaniem $z \leftarrow z^2 + c$ aby osiągnąć nieograniczoną rosnącą sekwencję. szczegółowe sprawozdanie i ankietę można znaleźć w [1], który ukazał się w czasopiśmie fizyki, ale z dużym wykorzystaniem koncepcji TCS, np. Turing Machines itp., wczesne odniesienie [2] autorstwa Blum stwierdza, że zestaw Mandelbrota nie jest rozstrzygalny.

[1] Niedostępność i nierozstrzygalność w obliczeniach, geometrii i systemach dynamicznych Asaki Saito, Kunihiko Kaneko

[2] Teoria obliczeń i złożoność w stosunku do liczb rzeczywistych Lenore Blum, 1990

vzn
źródło

0

Nister, Hartley i Stewenius wykorzystali teorię Galois do udowodnienia optymalności niektórych algorytmów w wizji komputerowej. Ta praca nie jest ściśle związana z analizą złożoną, ale jest z nią ściśle związana $\mathbb{C}$ z powodu podstawowego twierdzenia algebry.

Reb.Cabin
źródło

Kompleksowa analiza w informatyce teoretycznej

Odpowiedzi: