Analiza matematyczna i złożoność obliczeniowa?

złożoność obliczeniowa obejmuje duże ilości kombinatoryki i teorii liczb, niektóre elementy stochastyczne i pojawiającą się ilość algebry.

Jednak będąc analitykiem zastanawiam się, czy istnieją zastosowania analizy w tej dziedzinie, czy może pomysły inspirowane analizą. Wiem tylko, co nieco to odpowiada, to transformata Fouriera na grupach skończonych.

Możesz mi pomóc?

Flajolet i Sedgewick opublikowali książkę „Analytic Combinatorics” http://algo.inria.fr/flajolet/Publications/AnaCombi/anacombi.html . Nie wiem dużo na ten temat, ale ludzie w terenie korzystają z narzędzi złożonych analiz. Jak dotąd ich aplikacje wydają się bardziej na analizie algorytmów niż na złożoności obliczeniowej.

Algorytmy Monte Carlo Markov Chain są przydatnym narzędziem do znajdowania algorytmów aproksymacyjnych. Niektóre techniki pokazujące, że te łańcuchy Markowa są inspirowane lub pochodzą bezpośrednio z analizy - na przykład patrz rozdział dotyczący szacowania objętości wypukłego ciała w książce Marka Jerruma o liczeniu .

Istnieją analityczne podejścia do lematu Szemerédiego, który ma uroczą aplikację do kombinatorycznego testowania właściwości. Lemma Szemerédiego dla analityka ma losowy algorytm znajdowania słabo regularnej partycji wykresu; zobacz także Granice wykresu i Testowanie parametrów .

Analiza funkcjonalna odgrywa coraz większą rolę w teorii osadzania metrycznego. Chociaż trudno jest wymienić wszystkie aspekty interakcji, głównym tematem jest wykorzystanie metod analizy funkcjonalnej do zrozumienia, w jaki sposób metryki osadzają się w normowanych przestrzeniach. Ten ostatni problem pojawia się w najrzadszym problemie cięcia, który jest ważnym problemem optymalizacji wykresu.

Aby uzyskać więcej informacji, dobrym źródłem jest cokolwiek autorstwa Assaf Naor .

Nie chodzi o złożoność obliczeniową, ale mimo to jest interesująca

Niektóre podejścia do semantyki obliczeń nieskończonych oparte są na przestrzeniach metrycznych. Google „semantyka przestrzeni metrycznej” pojawia się bardzo często. Jedno (stare) odniesienie na ten temat to Control Flow Semantics autorstwa de Bakkera i de Vinka. Niektóre ostatnie prace zostały wykonane przez nasz własny Neel , a mianowicie Ultrametric Semantics for Reactive Programs . Obszar ten bardzo różni się od opisanych powyżej, ale pojęcia z analizy z pewnością znajdą tu swoje miejsce.

Zasób ograniczony miarą teoria opracowana przez Jacka Lutz to doskonałe miejsce dla ludzi, którzy mają tła w analizie pracować. Oryginalny papier

Niemal wszędzie wysoka niejednorodna złożoność , Jack H. Lutz, Journal of Computer and System Sciences, 1992.

uogólnij pojęcie miary Lebesgue'a na klasy złożoności, a wiele kolejnych prac można znaleźć w Internecie.

$\mathsf{P}$$\mathsf{NP}$$\mathsf{ESPACE} = \mathsf{DSPACE}[2^{O(n)}]$$\mathsf{P}$$\mathsf{NP}$$\mathsf{P} \neq \mathsf{NP}$$\mathsf{ESPACE}$$\Omega(2^n/n)$$\mathsf{ESPACE}$

Ludzie pracujący w różnych obszarach informatyki mogą korzystać z różnych podpunktów analizy.

Aby dać konkretny przykład, opiszę mój własny przypadek. Prowadzę badania w podstawach kryptografii. W tym polu (jak również w złożoności obliczeniowej) znajduje się konstrukcja zwana losową wyrocznią (patrz także ta strona ). Jego różne właściwości są czasami badane przy użyciu narzędzi z teorii miary , która jest podpolą analizy. Takie leczenie można znaleźć w tym artykule , a także w kilku cytowanych artykułach.

Możesz także rzucić okiem na podstawy algebry i analizy dla informatyki autorstwa Jeana Galliera. To książka w toku, która mówi ci, co nowego w tej dziedzinie.

Uważam, że najlepszy związek między analizą matematyczną a teorią złożoności znajduje się w modelu obliczeń rzeczywistych Bluma i in. Nadal problemem jest oddzielenie NP_R od P_R, gdzie dwie klasy są zdefiniowane w rzeczywistym modelu obliczeniowym, w którym każda liczba rzeczywista jest bytem, ​​a jedna regularna operacja (+, -, *, /) wykonuje jeden krok.