Referencje dla technik proofingu TCS

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.

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:

• Technika samowyredukowalności.
• Technika funkcji jednokierunkowej.
• Turniejowa technika dzielenia i podbijania.
• Technika izolacji.
• Technika redukcji świadków.
• Technika interpolacji wielomianowej.
• Technika Nonsolvable Group.
• Technika losowych ograniczeń.
• Technika wielomianowa.

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 .

Sanjeev Arora ma dobry zestaw notatek, które nazywa „ zestawem teoretyków”

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/

Istnieje wiki poświęcona różnym technikom dowodowym: http://www.tricki.org/ (wydaje się być zainspirowana Timothy Gowers).

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.

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

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

• Jak udowodnić, że język nie jest regularny?
• Jak udowodnić, że język nie jest pozbawiony kontekstu?
• Jak przekonwertować skończone automaty na wyrażenia regularne?
• Rozwiązywanie lub aproksymacja relacji powtarzalności dla sekwencji liczb

Mamy też Jak nie rozwiązać P = NP? który jest bardziej o anty-technikach.

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.