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

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