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


79

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.


14
Radziłbym, abyś zaczął czytać standardowy tekst na temat teorii złożoności, taki jak Arora / Barak lub Papadimitriou, a gdy tylko utkniesz, ponieważ nie rozumiesz matematyki, spróbuj dowiedzieć się więcej na temat związanej z nią matematyki, zanim przejdziesz dalej.
Robin Kothari,

8
Po zrobieniu tego, co sugerował Robin, zacznij pracować nad małymi otwartymi problemami. Poczujesz się pobudzony do nauki matematyki, która się za tym kryje. Jako student nie uważam za bardzo skuteczną naukę matematyki tylko ze względu na naukę.
Alessandro Cosentino

Odpowiedzi:


53

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ą.


20
Ta odpowiedź nie oznacza, że ​​nie powinieneś studiować dziedzin, o których wiemy, że są ze sobą powiązane (zobacz inne odpowiedzi). Powiedziałbym, że obejmują one algebrę liniową, teorię grafów, teorię prawdopodobieństwa, podstawową algebrę abstrakcyjną i podstawową logikę.
Peter Shor,

6
Oczywiście, jeśli chcesz zrobić coś takiego, jak przyczynić się do programu Mulmuleya dotyczącego udowodnienia P NP, potrzebujesz dużo, wiele, dużo więcej matematyki niż to.
Peter Shor

34

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.


32

A C 0 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ń.AC0

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

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.


2
W tym samym duchu chcę wskazać pięknie napisany przewodnik po metodzie entropii „Entropia i liczenie” autorstwa Jaikumara Radhakrishnana. Metoda entropii jest kolejnym z tych zręcznych narzędzi, które są bardzo satysfakcjonujące, gdy stosuje się odpowiednią okazję.
arnab

27

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 ...


5
Większość rzeczy, których dopiero się uczysz, w zależności od tego, dokąd cię zaprowadzą badania / życie: z kursów, z wykładów, od współpracowników, z gazet itp.
Dana Moshkovitz

22

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.


Uwielbiam konkretną matematykę, ale jest trochę ezoteryczna. Najpierw poleciłabym bardziej popularną książkę, na przykład „Combinatorics” Camerona.
Emil

7
Oto moje wrażenie - Konkretna matematyka wydaje się być świetną książką do nauki dokładnej (lub prawie dokładnej) analizy algorytmów, mocnej strony Knutha. Jeśli to właśnie chcesz zrobić, kontynuuj. Należy jednak pamiętać, że większość prac z teorii złożoności podaje znacznie mniej precyzyjne granice, więc techniki CM są mniej istotne.
Andy Drucker

1
Niektórzy mogą powiedzieć, że dzieje się tak, ponieważ teoretycy złożoności są leniwymi dupkami. Ale myślę, że dzieje się tak, ponieważ (a) dokładne granice mogą wymagać więcej wysiłku niż warte, (b) często istnieje tak duża różnica między znanymi górnymi i dolnymi granicami, że małe udoskonalenia po obu stronach mogą wydawać się mało wartościowe.
Andy Drucker

Powinienem powiedzieć, że w książce jest wiele fajnych rzeczy - moje uwagi dotyczą głównie materiału na temat dokładnych rozwiązań sumowania i relacji powtarzalności.
Andy Drucker

22

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.


20

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.


18

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.


4
Popieram tę odpowiedź. Niezależnie od tego, którą matematykę uważasz za najciekawszą, poprowadzi Cię ona do najbardziej interesujących problemów, a także problemów, które możesz rozwiązać.
Derrick Stolee



9

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.


6

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)

Sn


nie zapomnij o deterministycznych konstrukcjach grafów ekspanderów
Sasho Nikolov

Masz na myśli konstrukcje algebraiczne wykorzystujące właściwość (T) a la Lubotzky? W takim przypadku jest to nieco inny smak niż w powyższych przykładach (nie używaj niedopasowań skończonych grup).
Marcin Kotowski

4

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.


1
Nauczyłem się złożoności z tej książki, ale uważam, że jest niezrównoważona, z wieloma dziwacznymi, ale ostatecznie nieistotnymi szczegółami, ale brakuje w niej opisu zagadnień, które były ważne nawet w momencie pisania książki. Z drugiej strony jest to czasami ważna praca referencyjna. Natomiast tekst Kozen, o którym mowa w innej odpowiedzi, jest jasny, wyczerpujący i nowoczesny.
András Salamon,

1

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).


2
Chciałbym mieć wystarczającą reputację, aby głosować w dół. Dlaczego te odniesienia do jednego uniwersytetu i jego biblioteki?
Alessandro Cosentino

2
FWIW, QA267.G57 to numer wywoławczy Biblioteki Kongresu, który jest powszechnie stosowanym standardem bibliotecznym. Nie jest specyficzny dla University of Waterloo (z wyjątkiem ewentualnie ostatnich cyfr).
Emil Jeřábek
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.