Jakie podstawy matematyczne są potrzebne do teorii złożoności?

Obecnie jestem studentem, który w tym roku musi ukończyć studia. Po ukończeniu studiów rozważam pracę w kierunku magistra / doktora TCS. Zacząłem się zastanawiać, jakie dziedziny matematyki są uważane za pomocne w TCS, zwłaszcza (klasyczna) teoria złożoności.

Jakie dziedziny uważasz za niezbędne dla kogoś, kto chce studiować teorię złożoności? Czy znasz jakieś dobre podręczniki dotyczące tych dziedzin, a jeśli tak, podaj poziom trudności (wprowadzający, magisterski itp.).

Jeśli rozważasz pole, które nie jest intensywnie wykorzystywane w teorii złożoności, ale uważasz, że ma ono zasadnicze znaczenie dla TCS, zapoznaj się z nim.

Jeśli spojrzysz na odpowiedzi na to pytanie TCS StackExchange , zobaczysz, że istnieje możliwość, że praktycznie każda dziedzina matematyki może być ważna w teorii złożoności. Tak więc, jeśli naprawdę interesujesz się jakąś dziedziną matematyki, która nie wydaje się być powiązana, idź dalej i przestudiuj ją. Jeśli kiedykolwiek stanie się to istotne dla teorii złożoności, będziesz jednym z niewielu teoretyków złożoności, którzy ją rozumieją.

Do swojej listy powinieneś dodać książkę Dextera Kozen'a na temat teorii obliczeń. Bardzo skutecznie obejmuje podstawy teorii złożoności, a krótki format wykładu jest świetny.

Jeśli chodzi o podstawy matematyczne, oprócz tego, co wspomniano powyżej:

• Teoria prawdopodobieństwa
• Algebra liniowa i algebra abstrakcyjna
• teoria grafów
• podstawowa logika

Nie sądzę, że musisz być mistrzem tych tematów, aby na początku, ale zdecydowanie pomaga mieć pewien poziom komfortu.

A C $\bullet$ Książka Extremal Combinatorics autorstwa Stasysa Jukny jest zbyt mało znana IMO w społeczności złożonej. To świetny zbiór technik kombinatorycznych napisanych głównie z myślą o ich zastosowaniach w TCS (głównie złożoność). Wiele ważnych technik złożoności jest omawianych w kontekście kombinatoryki, w tym słynne wyniki, takie jak dolne granice obwodu monotonicznego i , ale także kilka bardzo dobrych wyników, których w innym przypadku nie można spotkać. I jest wiele ćwiczeń.$AC^0$

Jest to (według mojej wiedzy) jedyna opublikowana książka, która dogłębnie traktuje „metodę algebry liniowej w kombinatoryce” - zręczne, potężne narzędzie, o którym warto wiedzieć. Istnieje szkic manuskryptu Babai i Frankl, który idzie o wiele głębiej, ale nie został opublikowany ani w Internecie:

https://cs.uchicago.edu/page/linear-algebra-methods-combinatorics-applications-geometry-and-computer-science

$\bullet$ Jak zapewne wiesz, metoda probabilistyczna w kombinatoryce jest bardzo ważna, a nawet centralna, w teorii złożoności. Książka Jukny obejmuje ją, ale bardziej szczegółowo (z wieloma innymi pięknymi przykładami) jest ona opisywana przez słynną książkę Alona i Spencera The Probabilistic Method.

W poprzednich odpowiedziach wymieniono już te podstawowe: teoria prawdopodobieństwa, kombinatoryka, algebra liniowa, algebra abstrakcyjna (pola skończone, teoria grup itp.).

Dodałbym:

Analiza Fouriera , patrz np. Kurs Ryana O'Donnela: http://www.cs.cmu.edu/~odonnell/boolean-analysis/

Teoria kodowania , patrz kurs Madhu Sudana: http://people.csail.mit.edu/madhu/coding/course.html

Teoria informacji , standardowa książka to Elementy teorii informacji: http://www.amazon.com/Elements-Information-Theory-Telecommunications-Processing/dp/0471241954

Jest też teoria reprezentacji, losowe spacery i wiele innych, o których prawdopodobnie zapomniałem ...

Oprócz podstawowych rzeczy, prawdopodobnie:

• Kombinatoryka - możesz często liczyć rzeczy
• Stochastyka - do analiz średnich przypadków i algorytmów losowych

Lubię konkretną matematykę Knutha. Daje dobry przegląd / podstawową wiedzę o wielu ważnych narzędziach.

Jeśli lubisz generowania funkcji (patrz generationfunctionology przez Wilf) jako narzędzie, analiza zespolona jest przydatna, too.

Sanjeev Arora ma fajny dokument na kurs (dla studentów I roku), którego nauczał, zwany „zestawem teoretyków”, który zawiera wiele podstawowych materiałów, które powinien znać student teorii. Wiele z tych rzeczy możesz poczekać do ukończenia szkoły, aby się uczyć, ale da ci to dobre wyobrażenie o tym, co musisz wiedzieć i jakie są warunki wstępne.

Powszechny, choć z pewnością nie uniwersalny, paradygmat dla wielu odnoszących sukcesy badaczy w społeczności TCS jest następujący: Poznaj kilka podstaw na poziomie licencjackim, takich jak logika, algebra liniowa, prawdopodobieństwo, optymalizacja, teoria grafów, kombinatoryka, podstawowa algebra abstrakcyjna. Poza tym nie zmuszaj się do uczenia się czegokolwiek innego, dopóki nie pomyślisz, że potrzebujesz go do rozwiązania tego problemu, z którym zmagałeś się od miesięcy, lub jeśli uważasz, że naprawdę lubisz uczyć się czegoś takiego.

„Skąd mam wiedzieć, że go potrzebuję, jeśli nigdy go nie widziałem?”, Pytasz? Dobre pytanie. Czasami masz szczęście i wyczuwasz: „Wiesz co, ten pod-problem, który staram się rozwiązać, brzmi bardzo podobnie do tego, że czteroletnia transformacja, o której Fred się nie zamyka. Będę musiał to sprawdzić lub złapać Freda w pułapkę. w pokoju i poproś go o szybkie zapoznanie się z podstawami. ” Innym razem uwięziłeś w pokoju grupę bardziej kompetentnych ludzi niż siebie, powiedz, prowadząc seminarium lub coś w tym stylu, i jęczałeś o tym, jak nie możesz rozwiązać tego problemu, dopóki Fred nie woła: „Hej, założę się, że ty mogę rozwiązać ten problem za pomocą analizy Fouriera. Pokażę ci, jak to zrobić ”. W końcu dostajesz wspólny artykuł z Fredem, nauczyłeś się czegoś nowego, a ty i Fred jesteście teraz najlepszymi kumplami i pijacie co drugi sobotni wieczór.

Myślę, że wykaz dziedzin matematyki, które nie przydatny byłby znacznie krótszy niż listy pól, które są! Nie mogę wymyślić żadnego.

Studiuj matematykę, która wygląda interesująco i / lub cokolwiek, co w tej chwili wygląda, czego potrzebujesz. Nawet jeśli nie użyjesz go bezpośrednio, pomoże ci to nauczyć się innych rzeczy, które robisz.

Znajomość podstawowej logiki matematycznej jest moim zdaniem plusem. Możesz rzucić okiem na dwie książki Cori i Lascara.

Logika matematyczna: kurs z ćwiczeniami Część I

Logika matematyczna: kurs z ćwiczeniami Część II

Polecam rzucić okiem na te książki:

• Princeton Companion to Mathematics
• Logika w informatyce; Modelowanie i uzasadnianie systemów

Ponadto tematy na konferencji MFCS (Mathematical Foundation of Computer Science) mogą doprowadzić do tego, jakiego rodzaju tła możesz potrzebować. (Zastrzeżenie: konferencja zawiera wysoce zaawansowane tematy. Nie musisz ich opanowywać. Spróbuj uzyskać pełny obraz.)

Teoria liczb nie została wspomniana, ale jest to bardzo ważne narzędzie dla wielu konstrukcji kryptograficznych i teoretycznych dotyczących złożoności.

Teoria reprezentacji grup skończonych (również nad polami skończonymi) może być zaskakująco przydatna do różnych zadań, w tym:

• algorytmy mnożenia macierzy ( Cohn - Kleinberg-Szegedy-Umans )

• konstruowanie kodów dekodowalnych lokalnie (patrz np. ten artykuł Klim Efremenko)

• zastosowania w obliczeniach kwantowych (problem ukrytej podgrupy dla grup nieabelowych, multiplikatywna metoda przeciwnika)

$S_n$

Polecam lekturę książki Gareya i Johnsona

Komputery i nienaruszalność: Przewodnik po teorii kompletności NP .

Można to odczytać z bardzo małym zapleczem matematycznym. Myślę, że przeczytanie tej książki jest przyjemnością i poleciłbym ją jako pierwszą książkę nad Papadimitriou i Arora / Barak. Po przeczytaniu tego możesz zanurzyć się w innych książkach i zidentyfikować różne fragmenty matematyki, których potrzebujesz, aby zrozumieć zaawansowane tematy, którymi jesteś zainteresowany.

Dawno, dawno temu na poziomie licencjackim CS464 (2002) w UWaterloo CS wykorzystano złożoność obliczeniową Christosa H. Papadimitriou , Addison-Wesley, 1994.

Wymienione tematy podstawowe obejmują maszyny Turinga, nierozstrzygalność, złożoność czasu i kompletność NP.

W tle przejrzyj swoją bibliotekę w pobliżu QA267.G57 (Goddard's Przedstawiamy teorię obliczeń , opartą na szybkim odczycie lub dwóch i jej dostępności, wydaje się, że pokrywa stronę CS tła; mam wrażenie, że zestaw i grupa przydatna byłaby teoria z czystej matematyki).