Я начинаю свою докторскую диссертацию этой осенью и планирую работать над теорией сложности для своей диссертации.
Я составляю список важных работ, которые должен знать каждый теоретик сложности.
Какие документы вы бы предложили человеку, как я? И, пожалуйста, кратко объясните, почему вы считаете эту статью важной.
cc.complexity-theory
reference-request
big-list
новый аспирант
источник
источник
Ответы:
Неравномерная цепь ACC Райана Уильяма Нижние границы и все приведенные в ней результаты.
Это не только недавний важный результат, это очень хорошо написанная статья. Кроме того, результаты, которые использует и цитирует статья, охватывают довольно хороший диапазон результатов семенной сложности. Поэтому, если вы проследите ссылки и прочтете их - дойдете до точки, в которой вы поймете каждую часть нижней границы ACC, исходя из первых принципов, - я думаю, это было бы отличным началом для обучения сложности выпускника.
источник
Хотя это не прямой ответ на ваш вопрос, я хотел бы порекомендовать следующую книгу:
Большинство его глав связаны с теорией сложности. Книга может рассматриваться как хорошая коллекция результатов некоторых важных научных работ. Вы можете получить документы по результатам!
источник
Я бы порекомендовал результаты в
Компаньон по теории сложности Хемаспандры и Огихары.
Он организован вокруг методов, а не результатов, хотя часто метод был разработан для определенного результата, и он охватывает несколько оригинальных результатов и важных методов доказательства.
источник
1) R. Ладер, Н. Линч и А. Сельман. Сравнение полиномиальных временных сводок. Теоретическая информатика, 1 (2): 103-124, 1975.
2) Л.Г. Валиант «Сложность вычисления перманента», Теоретическая информатика, 8 (1979), с. 181-201.
3). Бласс и Ю. Гуревич «Об однозначной проблеме выполнимости». Информация и контроль, 55 (1-3) стр. 80-88, 1982.
4) J. Balcazar, R. Book & U. Schoning. «Иерархия полиномиального времени и редкие оракулы», журнал Associate Computing Machinery, том 33, №3. July1986. страницы 603-617.
5) LG Valiant & V. Vazirani «NP - это так же просто, как обнаруживать уникальные решения» Теоретическая информатика 47 (1986) стр. 85-93.
6) Е. Аллендер. Сложность разреженных множеств в P. В трудах 1-й структуры по теории сложности конференции, стр. 1-11. Springer-Verlag Конспект лекций в области компьютерных наук № 223, июнь 1986 г.
6) R. Beigel. О релятивизированной мощности дополнительных приемных путей. В материалах 4-й конференции «Структура в теории сложности», стр. 216-224. IEEE Computer Society Press, июнь 1989 г.
7) Р.Бейгель и Дж. Гилл «Классы подсчета: пороги, четность, моды и немногочисленность» Теоретическая информатика, том 103, стр. 3-23. 1992.
8) S. Феннер, Л. Фортнау и С. Курц Журналы компьютерных и системных наук, том 48, стр. 116-148, 1994. Журналы компьютерных и системных наук.
9) R. Beigel, H. Buhrman и L. Fortnow. NP может быть не так просто, как обнаружение уникальных решений. В материалах 30-го симпозиума ACM по теории вычислений, стр. 203-208. ACM Press, май 1998 г.
10) B. Borchert, L. Hemaspaandra & J. Rothe «Достаточность ограниченного принятия для проблем эквивалентности» LMS J Comput. Математика 3 Страницы 86-95 2000.
источник
Я согласен с ответом Абузера выше: я думаю, что каждая глава книги о вычислительной сложности (например, Арора и Барака « Вычислительная сложность: современный подход » или « Вычислительная сложность Голдрейха : концептуальная перспектива ») содержит (и часто объясняет более ясно кстати) результаты, которые приходят из важных / фундаментальных работ. И, читая книгу по вычислительной сложности, вы можете лучше понять, почему они считаются важными.
Однако это мои любимые:
Теорема Савича: Савич, Уолтер Дж. (1970), «Отношения между недетерминированными и детерминированными сложностями ленты», Журнал компьютерных и системных наук 4 (2): 177–192, DOI: 10.1016 / S0022-0000 (70) 80006-X
Теорема Кука-Левина : Кук, Стивен (1971). « Сложность процедур доказательства теорем ». Материалы третьего ежегодного симпозиума ACM по теории вычислений. С. 151–158
Дж. Хопкрофт, В. Пол и Л. Валиант, « О времени и пространстве» , J. ACM, 24, 332–337 (1977)
Т. П. Бейкер, Дж. Джилл, Р. Соловай. Релятивизация P =? Н.П. Вопрос. Журнал SIAM по вычислительной технике, 4 (4): 431-442 (1975)
источник