Недавно я начал много читать о сложности доказательств, и мне очень понравилось то, что я читал. Я действительно хотел бы узнать больше об этом, но мне трудно найти хороший материал для начинающих. Кто-нибудь сможет порекомендовать некоторые основы?
cc.complexity-theory
lo.logic
proof-complexity
Югио Мисима
источник
источник
Ответы:
Это зависит от того, какой уровень «новичка» вы хотите иметь. Я не думаю, что есть действительно хороший текст уровня бакалавриата о сложности доказательств (это, вероятно, верно для большинства специализированных подразделов по сложности). Но для начинающих (выпускников) источников я бы порекомендовал что-то вроде хорошего понимания базового экспоненциального нижнего предела размера для опровержений разрешения принципа голубя (через случайные ограничения, компромисс между шириной и выполнимой интерполяцией), а также расширить его от этого. указать дальше. Это может быть достигнуто (приблизительно) следующим образом:
Стасис Юкна, Экстремальная комбинаторика с приложениями в информатике, 2001, Springer-Verlag, раздел 4.8.
Эли Бен-Сассон и Ави Вигдерсон, Короткие доказательства - узкие - резолюция упрощена (2000), JACM.
П. Бим и Т. Питасси, Сложность доказательства предложений: прошлое, настоящее и будущее, Современные тенденции в теоретической информатике: начало XXI века (Г. Пол, Г. Розенберг и А. Саломаа, редакторы), World Scientific Publishing , 2001, с. 42--70.
Павел Пудлак, Нижние оценки для разрешений и разрезания плоскостей доказательств и монотонных вычислений, Журнал символической логики, том. 62 (1997), нет. 3, с. 981-998.
Вы также можете обратиться к более самодостаточному и длинному тексту:
Для более логичной стороны сложности доказательства, как предложил Каве, вы можете начать читать первые главы:
источник
Для более алгебраической стороны сложности доказательства я рекомендую начать с обзорной статьи Питасси 1996 года:
Для быстрого обзора вы также можете обратиться к главе 5 книги Клота - Кранакиса, уже упомянутой Иддо, в которой есть раздел, посвященный алгебраическим системам доказательства.
Первая исследовательская статья, которую я бы рекомендовал прочитать (и потому, что она оригинальна, и потому что она приятна для чтения) - это статья, в которой была введена система доказательства Гребнера или полиномиального исчисления:
источник
Я нахожу эти вводные заметки лекцией легкими для чтения: лекции Пола Бима по IAS
источник
Самое последнее и современное исследование сложности доказательств общего назначения, вероятно, проведено Натаном Сегерлиндом:
Натан Сегерлинд: сложность пропозициональных доказательств. Бюллетень символической логики 13 (4): 417-481, 2007 ( http://www.math.ucla.edu/~asl/bsl/1304/1304-001.ps ).
А теперь предупреждения для двух бесстыдных самовывозов ...
Еще более недавний опрос, но более узкий, сфокусированный на вопросах, касающихся размера доказательств, пространства доказательств и компромиссов между размерами, состоит в следующем:
Якоб Нордстрем. Игры с галькой, сложность доказательств и пространственно-временные компромиссы. Логические методы в информатике, том 9, выпуск 3, статья 15, сентябрь 2013 г. ( http://www.lmcs-online.org/ojs/viewarticle.php?id=674 ).
Есть также некоторые лекционные заметки из моего недавнего курса по «низкоуровневому спектру» сложности доказательств (т. Е. Сравнительно слабых систем доказательств, таких как разрешение, полиномиальное исчисление и плоскости разреза) и связям с решением SAT. Эти заметки можно найти по адресу http://www.csc.kth.se/~jakobn/teaching/proofcplx11/#scribe-notes (некоторые еще находятся в разработке, но те, которые доступны, должны быть в хорошей форме).
источник