Некрологи мертвых догадок

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

1. Гипотеза случайного оракула: отношения между классами сложности, которые имеют место почти для всех релятивизированных миров, также имеют место в нерелятивизированном случае. Это было опровергнуто результатом и показом того, что I P X ≠ P S P A C E X справедливо почти для всех случайных оракулов X , см . Гипотеза о случайном оракуле неверна .$IP=PSPACE$$IP^X\neq PSPACE^X$$X$

2. Ограниченная случайность ошибок должным образом расширяет степень полиномиального времени (т. Е. ). Некоторое время это считалось, но позже, из-за сложных результатов дерандомизации и их связи со сложностью схемы, стала распространяться противоположная гипотеза ( P = B P P ) (хотя она все еще открыта).$P\neq BPP$$P=BPP$

Какие еще предположения не прошли проверку временем?

$\mathsf{NL} \neq \mathsf{coNL}$ . До того, что эти два были равны, я думаю, что было широко распространено мнение, что они различны, по аналогии с убеждением, что (то есть общий принцип, что «недетерминизм и ко «недетерминизм различен»; это оказалось ложным при ограничениях сложности пространства, которые были хотя бы логарифмическими).$\mathsf{NP} \neq \mathsf{coNP}$

До считалось возможным, что даже не содержался в : в Fortnow-Sipser 1988 они предположили, что это так, и дали оракул, относительно которого это было правдой.$\mathsf{IP} = \mathsf{PSPACE}$$\mathsf{coNP}$$\mathsf{IP}$

Для программ ветвления с постоянной шириной требуется больше, чем полиномиальная длина : после того, как Furst-Saxe-Sipser и Ajtai в 1981 году показали, что цепи AC ⁰ не могут считать, естественным следующим шагом было показать, что программы ветвления с постоянной шириной полинома длина не может сосчитать, что было широко распространено предположить, чтобы держать. Дэвид Баррингтон в 1986 году показал, что они не только могут считать, но и эквивалентны NC ¹ .

Гипотеза : что для любого детерминированного алгоритма для требуется время .$\mathsf{3SUM}$$\mathsf{3SUM}$$\Omega(n^2)$

Это было опровергнуто в 2014 году Алланом Грёнлундом и Сетом Петти, которые дали детерминированный алгоритм, который выполняется за времени [1].$O(n^2/(\log n/\log \log n)^{2/3})$

[1] Втроем, вырождения и любовные треугольники. Аллан Грёнлунд и Сет Петти. В Основы информатики (FOCS) 2014, с. 621-630. arXiv: 1404.0799 [cs.DS]

Решение десятой проблемы Гильберта Дэвисом, Матиясевичем, Путнэмом и Робинсоном, показывающее, что рекурсивно перечислимые множества являются именно диофантовыми множествами.

(Я воспроизвожу здесь сообщение в блоге , задним числом , пару лет назад, как это было предложено в комментариях.)

Из обзора Георга Крейзеля о задаче решения для экспоненциальных диофантовых уравнений , выполненного Мартином Дэвисом, Хилари Патнэм и Джулией Робинсон, Ann. математики (2), 74 (3) , (1961), 425–436. MR0133227 (24 # A3061) .

Эта статья устанавливает, что каждый рекурсивно перечислимый (пере) набор может быть экзистенциально определен в терминах возведения в степень. […] Эти результаты поверхностно связаны с десятой проблемой Гильберта о (обыкновенных, то есть неэкспоненциальных) диофантовых уравнениях. Доказательство результатов авторов, хотя и очень изящное, не использует тайных фактов ни в теории чисел, ни в теории множеств, и поэтому вполне вероятно, что настоящий результат не тесно связан с десятой проблемой Гильберта. Также не совсем правдоподобно, что все (обычные) диофантовы задачи равномерно сводятся к задачам с фиксированным числом переменных фиксированной степени, что было бы в случае, если бы все повторы были диофантовыми.

Конечно, моя любимая цитата в отношении десятой проблемы - от Предисловия Мартина Дэвиса к десятой проблеме Гильберта Юрия Матиясевича .

В 1960-е годы мне часто приходилось читать лекции по десятой проблеме Гильберта. В то время было известно, что неразрешимость будет следовать из существования единственного диофантова уравнения, удовлетворяющего условию, сформулированному Джулией Робинсон. Тем не менее, казалось, что чрезвычайно трудно создать такое уравнение, и действительно, преобладающее мнение заключалось в том, что оно вряд ли существует. В своих лекциях я бы подчеркнул важные последствия, которые вытекают из доказательства или опровержения существования такого уравнения. Неизбежно в течение периода вопросов меня спросили бы, каково будет собственное мнение относительно того, как все обернется, и я был готов к ответу: «Я думаю, что гипотеза Джулии Робинсон верна, и она будет подтверждена умным молодым русским».

Программа Гильберта и его «гипотеза» о разрешимости формальных теорий. Он был сформулирован в начале 1920-х годов и проводился им и его сотрудниками в Геттингенском университете и в других местах в 1920-х и 1930-х годах.

«С этим новым основанием математики, которое можно соответствующим образом назвать теорией доказательств, я полагаю, что раз и навсегда избавлюсь от основополагающих вопросов математики как таковых, превратив каждое математическое утверждение в конкретную экспонируемую и строго выводимую формулу и перенеся тем самым целый комплекс вопросов в области чистой математики ".

Хорошо известно, что предложения Гильберта «врезались» (довольно быстро [1931]) в теорему Гёделя о неполноте .

Для хорошего обзора программы Гильберта и последующих событий см .: Ричард Зак; Программа Гильберта тогда и сейчас; Справочник по философии науки. Том 5: Философия логики; 2006

См. Также ответ Андреса Кайседо о другом аспекте этой истории: десятой проблеме Гильберта, которая была решена только в 1970 году.

В лекции Мадху Судана * он утверждал, что существует некое убеждение, что существует такое , что через полуопределенное программирование, до доказательства трехбитной теоремы Хостада о PCP.$s > 1/2$$\text{PCP}_{1,s}[ \log n, 3] \subseteq \text{P}$

Действительно, SDP показывает , что дает жесткую оценку сложности таких PCP.$\text{PCP}_{1,1/2}[ \log n, 3] = \text{P}$

(* Я нашел эту лекцию Мадху, опубликованную в «Вычислительной теории сложности» под редакцией Рудича / Вигдерсона »)

гипотезы варьируются по спектру от формального до неформального. например, знаменитая гипотеза Гильбертса о разрешимости математики была формализована в несколько задач, например, 10-я задача Гильберта, но это была также более грандиозная неформальная гипотеза, охватывающая всю область. это также можно рассматривать как предлагаемую исследовательскую программу.

Один простой рецепт, чтобы найти такой «некролог мертвых догадок» - это рассмотреть «мета-утверждение», что гипотеза [x] может быть доказана при моей жизни ». Математическая литература полна таких утверждений / ожиданий, которые оказались «ложными» в том смысле, что они полностью игнорировали ожидания в отношении сложности и доступности доказательства. классической является гипотеза Римана, открытая более 1,5 лет. Применение этой же модели к теории сложности не так просто, потому что теория сложности является гораздо более молодой научной областью. однако вот ключевой пример.

раннее обнаружение проблемы P vs NP (теперь открытой 4½ десятилетия) имело своего рода невинность в том смысле, что первоначальные исследователи не представляли и не могли вообразить, насколько трудной или сквозной может оказаться проблема. чтобы сделать это более конкретным, рассмотрим область сложности схем, изобретенную в начале 1980-х годов, например, Sipser. это была исследовательская программа, похожая на Хилбертса, который был частично создан для нападения на П против NP. некоторые исторические результаты суммированы Арвиндом в этом резюме / введении . Столбец вычислительной сложности, BEATCS 106 :

1980-е годы были золотым периодом для нижних границ сложности булевой схемы. Были крупные прорывы. Например, нижняя граница экспоненциального размера Разборова для монотонных булевых цепей, вычисляющих функцию Клика, и нижние границы суперполиномиального размера Разборова-Смоленского для цепей постоянной глубины с модулями MOD _p для простого p. Эти результаты внушают исследователям оптимизм в отношении прогресса в вопросах, связанных с нижними границами и разделением классов сложности. Однако в последние два десятилетия этот оптимизм постепенно превратился в отчаяние. Мы до сих пор не знаем, как доказать суперполиномиальные нижние оценки для цепей постоянной глубины с вентилями MOD ₆ для функции, вычисляемой за экспоненциальное время.

было два ключевых документа, которые сбивали надежды в этой области. Разборов имел отличные / знаменитые результаты по функции Клика, но затем написал две противоположные статьи. в одной статье показано, что согласование, проблема P-времени, требует экспоненциальных монотонных цепей, и поэтому в некотором смысле подход монотонных цепей к нижним границам был сорван из-за несоответствия в сложности с немонотонными («полными») цепями (все еще не полностью понял).

это было расширено в его знаменитой статье « Естественные доказательства», в соавторстве с Рудичем, в которой показано, что все доказательства нижних границ предыдущих схем подчиняются определенному шаблону, который имеет доказуемую слабость в смысле конфликта с предполагаемыми нижними оценками на жестких генераторах случайных чисел из криптография.

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