Удивительные результаты в сложности (нет в списке блогов сложности)

Каковы были самые удивительные результаты в сложности?

Я думаю, что было бы полезно иметь список неожиданных / неожиданных результатов. Это включает в себя как результаты, которые были неожиданными и появились из ниоткуда, так и результаты, которые оказались не такими, как ожидалось.

Редактировать : учитывая список, разработанный Gasarch, Lewis и Ladner в блоге сложности (на который указывает @Zeyu), давайте сосредоточим вики этого сообщества на результатах, которых нет в их списке. Возможно, это приведет к фокусировке на результатах после 2005 года (согласно предложению @ Jukka).

Пример: слабое обучение = сильное обучение [Schapire 1990] : (Удивительно?) Наличие какого-либо преимущества над случайным угадыванием дает вам обучение PAC. Привести к алгоритму AdaBoost.

Вот гостевой пост Билла Гасарха с помощью Гарри Льюиса и Ричарда Ладнера: http://blog.computationalcomplexity.org/2005/12/surprising-results.html

Если , то для этого есть «диагональное» доказательство.$P \neq NP$

Этот результат обусловлен Козен. Не все согласны с тем, что он называет доказательством диагонализации.

В «Барьерах I» группа ведущих теоретиков сложности согласилась с тем, что теорема Баррингтона была результатом, который их больше всего удивил. Фортноу объясняет теорему Баррингтона здесь: http://blog.computationalcomplexity.org/2008/11/barringtons-theorem.html

$NL$ закрыто в соответствии с дополнением.

Я бы сказал, что недавние работы Jain, Upadhyay и Watrous показали, что QIP = IP = PSPACE довольно удивительно. Мое мнение таково, что не столько интересен QIP = IP, сколько факт, что весь QIP может быть смоделирован в 3-раундовом квантовом интерактивном доказательстве. Довольно крутая демонстрация силы квантового параллелизма.

Что-то, что продолжает удивлять меня, - то, что BPP, вероятно, будет P - Это поднимает много философских вопросов относительно природы случайности.

Теоремы Гёделя о неполноте

Теорема Разборова-Рудича о естественных доказательствах.

(AFAIK) Люди очень надеялись доказать нижние границы схемы, но после этой теоремы многие перестали работать и перешли к другим темам.

Счетная версия проблемы Monotone-SAT # P-complete.

Экземпляр Monotone-SAT - это пропозициональная формула со следующим ограничением: каждая переменная либо всегда бывает положительной, либо всегда отрицательной (другими словами, каждый литерал в является чистым литералом).$F$$F$

Я был очень удивлен этим результатом, потому что вариант решения проблемы Monotone-SAT тривиален.

Широко известно, что существуют проблемы решения в P, чьи версии подсчета # P-полны (один пример - 2-SAT). Но, на мой взгляд, этот случай немного «другой»: найти удовлетворительное назначение экземпляра Monotone-SAT не только легко (как, например, найти удовлетворительное назначение экземпляра 2-SAT), но и существенно тривиально. Не просто: тривиально, буквально. Обратите внимание, что, например, с учетом экземпляра 2-SAT он может быть либо удовлетворительным, либо неудовлетворительным; хотя, имея экземпляр Monotone-SAT, вы заранее знаете, что он, безусловно, выполним: он не может быть неудовлетворенным, ни в коем случае: это подтверждает, что даже обе проблемы просты, их уровни «простоты принятия решений» различны. С другой стороны, их уровни «счета-беспокойства» точно такие же.

Этот сильный контраст между следующими фактами

1. Решить, Monotone-SAT глупо тривиально
2. Подсчет Monotone-SAT чрезвычайно сложен

ИМХО как минимум увлекательно.

Что аксиомы выбора и определения не совместимы.