Существуют ли какие-либо ссылки (онлайн или в форме книги), которые организуют и обсуждают теоремы TCS методом доказательства? Garey и Johnson делают это для различных видов конструкций виджетов, необходимых для доказательства NP-полноты (особенно в главе 3 их книги), но мне интересно, есть ли что-нибудь, что рассматривает методы доказательства в TCS более широко.
Так, например, темы могут включать диагонализацию, разбитую далее по типу используемой конструкции; доказательства по истории вычислений; табличные конструкции; аргументы о несжимаемости и т. д. Я полагаю, что я мог бы просто расколоть стандартную теорию вычислительного текста и переставить разделы, но было бы замечательно, если бы там было что-то, что также предоставляет некоторые дополнительные комментарии и показывает, где существуют общие черты между этими методами. используемый.
Просто чтобы быть ясным, поскольку в любом тексте будут использоваться доказательства, я действительно заинтересован в поиске ссылки, в которой сами методы доказательства являются предметом обсуждения.
В дополнение к главе 3 Гэри и Джонсона, вот еще один частный пример, который мне только что пришёл в голову: в Ли и Витаньи в главе 6 они обсуждают метод несжимаемости и приводят примеры того, как применять эту технику.
Ответы:
Компаньон по теории сложности Хемаспандры и Огихары . Она не является исчерпывающей с точки зрения техники (я думаю, что такой книги нет), но я думаю, что она квалифицируется как ответ на ваш вопрос. Вот названия глав:
источник
Вот еще одна книга, где главы больше сосредоточены на методах доказательства.
«Экстремальная комбинаторика с приложениями в информатике», Стасис Юкна. Это хорошая книга, в которой рассказывается о многих комбинаториках, которые могут вам понадобиться в TCS. Конечно, его предмет не включает диагонализацию, таблицы и т. Д., Но представляет собой набор аккуратных комбинаторных техник, ищущих приложение (и в разных местах в тексте приложения прописаны).
«Ранний черновик» второго издания доступен здесь .
источник
У Санджива Арора есть хороший набор заметок, которые он называет «Инструментарий теоретика»
источник
Книга «Жемчужины теоретической информатики» - это хороший способ изучить множество различных методов (хотя вы видите, что каждый из них применяется только один раз):
http://www.calvin.edu/~rpruim/publications/gems/
источник
Существует вики, посвященная различным методам доказательства: http://www.tricki.org/ (кажется, вдохновлен Тимоти Гауэрсом).
источник
Другая техника, которая полезна во многих разделах теоретической информатики:
Нога Алон и Джоэл Х. Спенсер, Вероятностный метод (3-е издание), Wiley, ISBN 0470170204.
источник
С. Феннер, Л. Фортнов, С. Курц и Л. Ли. Инструментарий оракула. Информация и вычисления, 182 (2): 95-136, 2003. (также доступно с домашней страницы Лэнса ).
Это в основном обзорный документ об использовании универсальности при построении «дизайнерских оракулов» (то есть оракулов, разработанных с учетом различных свойств). Хотя это статья, я думаю, что она квалифицируется как ответ на вопрос, потому что она сосредоточена на технике и ее использовании, а не на каком-то конкретном результате. [Но это гораздо конкретнее, чем «Компаньон теории сложности», поэтому я подумал, что это должен быть отдельный ответ.]
источник
Мы начали некоторые справочные вопросы по cs.SE охватывающие типичные (пока что вводные) проблемы TCS. Помимо общей значимости, некоторые ответы содержат методы, которые могут быть известны не каждому исследователю, например:
У нас тоже есть Как не решить P = NP? что больше об анти-методах.
источник
В том же духе заметок Санджива Арора, которые разместил @umar, мне нравятся лекционные заметки Мадхура Тулсиани и упражнения для его класса «Математический инструментарий», размещенные на веб-странице курса . В дополнение к превосходному материалу Ароры в его заметках есть хороший обзор теории спектральных графов, а также метод обновления мультипликативных весов.
источник