Я хотел бы попросить предложения для хороших текстов, которые вводят сложность схемы. Любые ссылки на последние достижения и открытые проблемы в этой области также будут полезны.
15
Я хотел бы попросить предложения для хороших текстов, которые вводят сложность схемы. Любые ссылки на последние достижения и открытые проблемы в этой области также будут полезны.
Для начала, конечно, есть книга Ароры и Барака « Вычислительная сложность: современный подход» . Оттуда, части 3 и 4 книги Jukna « Сложность булевой функции: достижения и границы» являются отличным материалом для чтения. Кроме того, Райан Уильямс преподает хороший курс по сложности трасс, чьи записи можно надеяться выложить в Интернете :)
В дополнение к тем, которые предлагает Арнаб, я бы также порекомендовал следующую книгу:
источник
Модели вычислений Джона Э Сэвиджа (больше информации / детали / обзоры на Амазонке ). это в значительной степени больше учебника для студентов, но отличается своей ориентированной на цепь точки зрения. включает в себя множество расширенных тем / доказательств, а также бесплатную онлайн-версию и очень хорошо содержит гиперссылки (оглавление, ссылки, указатель и т. д.).
источник