Начните изучать сложность доказательства

12

Недавно я начал много читать о сложности доказательств, и мне очень понравилось то, что я читал. Я действительно хотел бы узнать больше об этом, но мне трудно найти хороший материал для начинающих. Кто-нибудь сможет порекомендовать некоторые основы?

Югио Мисима
источник
Вы проверили ссылки в статье доказательство сложности Википедии ? Книгу Стива и Фуонга относительно легко читать.
Каве
2
Мне понравилось выступление Олафа Бейерсдорфа в Хельсинки этим летом. Проверьте его слайды здесь .
Юхо

Ответы:

12

Это зависит от того, какой уровень «новичка» вы хотите иметь. Я не думаю, что есть действительно хороший текст уровня бакалавриата о сложности доказательств (это, вероятно, верно для большинства специализированных подразделов по сложности). Но для начинающих (выпускников) источников я бы порекомендовал что-то вроде хорошего понимания базового экспоненциального нижнего предела размера для опровержений разрешения принципа голубя (через случайные ограничения, компромисс между шириной и выполнимой интерполяцией), а также расширить его от этого. указать дальше. Это может быть достигнуто (приблизительно) следующим образом:

  1. Стасис Юкна, Экстремальная комбинаторика с приложениями в информатике, 2001, Springer-Verlag, раздел 4.8.

  2. Эли Бен-Сассон и Ави Вигдерсон, Короткие доказательства - узкие - резолюция упрощена (2000), JACM.

  3. П. Бим и Т. Питасси, Сложность доказательства предложений: прошлое, настоящее и будущее, Современные тенденции в теоретической информатике: начало XXI века (Г. Пол, Г. Розенберг и А. Саломаа, редакторы), World Scientific Publishing , 2001, с. 42--70.

  4. Павел Пудлак, Нижние оценки для разрешений и разрезания плоскостей доказательств и монотонных вычислений, Журнал символической логики, том. 62 (1997), нет. 3, с. 981-998.

Вы также можете обратиться к более самодостаточному и длинному тексту:

  • Питер Клот и Эвангелос Кранакис, булевы функции и вычислительные модели (глава 5)

Для более логичной стороны сложности доказательства, как предложил Каве, вы можете начать читать первые главы:

  • Стивен Кук и Фуонг Нгуен, Логические основы сложности доказательств (Перспективы в логике, Cambridge Press, 2010).
Иддо Цамерет
источник
1
Большое спасибо! Я покопаюсь в них и посмотрю, как они
получатся
6

Для более алгебраической стороны сложности доказательства я рекомендую начать с обзорной статьи Питасси 1996 года:

Для быстрого обзора вы также можете обратиться к главе 5 книги Клота - Кранакиса, уже упомянутой Иддо, в которой есть раздел, посвященный алгебраическим системам доказательства.

Первая исследовательская статья, которую я бы рекомендовал прочитать (и потому, что она оригинальна, и потому что она приятна для чтения) - это статья, в которой была введена система доказательства Гребнера или полиномиального исчисления:

Джошуа Грохов
источник
6

Я нахожу эти вводные заметки лекцией легкими для чтения: лекции Пола Бима по IAS

Дай Ле
источник
2
Заметки из лекций Пола Бима по МСФО очень хороши и дают хороший обзор области. Однако следует помнить, что существуют некоторые проблемы с некоторыми утверждениями теорем типа «если свиньи могут летать». Я попытался дать исправленные версии в (мини-опросе) главе 4 моей кандидатской диссертации: Якоб Нордстрем. Краткие доказательства могут быть простыми: понимание пространства в разрешении. Докторская диссертация, Королевский технологический институт, Стокгольм, Швеция, май 2008 г. ( www.csc.kth.se/~jakobn/research/PhDthesis.pdf ).
Якоб Нордстрем
5

Самое последнее и современное исследование сложности доказательств общего назначения, вероятно, проведено Натаном Сегерлиндом:

Натан Сегерлинд: сложность пропозициональных доказательств. Бюллетень символической логики 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 (некоторые еще находятся в разработке, но те, которые доступны, должны быть в хорошей форме).

Якоб Нордстрем
источник