Czy są jakieś odniesienia (online lub w formie książkowej), które organizują i omawiają twierdzenia TCS techniką dowodową? Garey i Johnson robią to dla różnych rodzajów konstrukcji widżetów potrzebnych do potwierdzenia kompletności NP (szczególnie w rozdziale 3 ich książki), ale zastanawiam się, czy jest coś, co traktuje techniki dowodzenia w szerszym kontekście.
Na przykład tematy mogą obejmować diagonalizację, w podziale według rodzaju zastosowanej konstrukcji; dowody z historii obliczeń; konstrukcje tableau; argumenty dotyczące nieściśliwości itp. Przypuszczam, że mógłbym po prostu pokroić standardową teorię tekstu obliczeniowego i zmienić kolejność sekcji, ale byłoby świetnie, gdyby istniało coś, co zapewnia również dodatkowy komentarz i pokazuje, gdzie są podobieństwa między technikami używany.
Żeby było jasne, ponieważ każdy tekst będzie wykorzystywał dowody, to, co naprawdę mnie interesuje, to odniesienie, w którym same techniki potwierdzania są prawdziwym przedmiotem.
Oprócz rozdziału 3 Garey i Johnsona, oto kolejny częściowy przykład, który właśnie przyszedł mi do głowy: w Li i Vitanyi , w rozdziale 6 omawiają metodę nieściśliwości i podają przykłady zastosowania tej techniki.
Odpowiedzi:
Towarzysz teorii teorii złożoności Hemaspaandra i Ogihara . Nie jest wyczerpujący pod względem technik (wydaje mi się, że nie ma takiej książki), ale myślę, że kwalifikuje się jako odpowiedź na twoje pytanie. Oto tytuły rozdziałów:
źródło
Oto kolejna książka, w której rozdziały koncentrują się bardziej na technikach dowodowych.
„Extremal Combinatorics with Applications in Computer Science”, autor: Stasys Jukna. To ładna książka i zawiera wiele kombinatoryki, których możesz potrzebować w TCS. Oczywiście jego przedmiot nie obejmuje diagonalizacji, tabel itp., Ale jest zbiorem schludnych technik kombinatorycznych poszukujących aplikacji (i w różnych miejscach tekstu, aplikacje są określone).
„Wczesny szkic” drugiej edycji jest dostępny tutaj .
źródło
Sanjeev Arora ma dobry zestaw notatek, które nazywa „ zestawem teoretyków”
źródło
Książka „Gems of Theoretical Computer Science” to dobry sposób na nauczenie się wielu różnych technik (chociaż widzisz, że każda z nich została zastosowana tylko raz):
http://www.calvin.edu/~rpruim/publications/gems/
źródło
Istnieje wiki poświęcona różnym technikom dowodowym: http://www.tricki.org/ (wydaje się być zainspirowana Timothy Gowers).
źródło
Kolejny tom technik, który jest przydatny w wielu częściach teoretycznej informatyki:
Noga Alon i Joel H. Spencer, The Probabilistic Method (3rd edition), Wiley, ISBN 0470170204.
źródło
S. Fenner, L. Fortnow, S. Kurtz i L. Li. Zestaw narzędzi budowniczych wyroczni. Information and Computation, 182 (2): 95-136, 2003. (dostępny również na stronie głównej Lance'a ).
Jest to w zasadzie artykuł przeglądowy na temat zastosowania ogólności w konstruowaniu „designerskich wyroczni” (to znaczy wyroczni zaprojektowanych tak, by miały różne właściwości). Chociaż jest to artykuł, myślę, że kwalifikuje się jako odpowiedź na pytanie, ponieważ koncentruje się na technice i jej zastosowaniach, a nie na jakimkolwiek konkretnym wyniku. [Ale jest to o wiele bardziej szczegółowe niż Towarzysz Teorii Złożoności, dlatego pomyślałem, że powinna to być osobna odpowiedź.]
źródło
Rozpoczęliśmy kilka pytań referencyjnych na temat cs.SE obejmujących typowe (jak dotąd wprowadzające) problemy TCS. Oprócz ogólnego znaczenia, niektóre odpowiedzi zawierają metody, które mogą nie być znane każdemu badaczowi, np .:
Mamy też Jak nie rozwiązać P = NP? który jest bardziej o anty-technikach.
źródło
W tym samym duchu notatek Sanjeeva Arory, które opublikował @umar, lubię notatki z wykładów i ćwiczenia Madhura Tulsianiego do jego lekcji „Zestaw narzędzi matematycznych” opublikowanej na stronie kursu . Oprócz doskonałego materiału Arory, jego notatki zawierają ładny opis teorii grafów spektralnych, a także metody aktualizacji wag multiplikatywnych.
źródło