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

44

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

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

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

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

Андрас Фараго
источник
3
coNPIP
4
Программа Гильберта («... раз и навсегда избавиться от основополагающих вопросов в математике как таковой ...») и его «гипотеза» о разрешимости формальных теорий [~ 1920], которые «разбились» (довольно быстро [1931] ]) в теорему Гёделя о неполноте :-)
Марцио Де Биаси
2
В обзоре Крейзеля эта статья гласит: «Эта статья устанавливает, что каждое рекурсивно перечислимое (пере) множество может быть экзистенциально определено в терминах возведения в степень.… Эти результаты поверхностно связаны с десятой проблемой Гильберта о (обыкновенной, то есть неэкспоненциальной ) Диофантовы уравнения ... ... не совсем правдоподобно, что все (обычные) диофантовы задачи равномерно сводятся к задачам с фиксированным числом переменных фиксированной степени, что было бы в случае, если бы все повторы были диофантовыми. " (См. Также здесь .)
Андрес Э. Кайседо
3
Также пост удивительные результаты из вычислительной сложности блога.
Каве

Ответы:

22

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

Джошуа Грохов
источник
«аналогия»? одно время, а другое пространство нет?
7
@ Арул: Да. Это аналогия между классами сложности, определяемыми ограничивающим временем, и классами сложности, определяемыми ограничивающим пространством ...
Джошуа Грохов
Но время и пространство не эквивалентны (по крайней мере предположительно)
25
@ Арул: Верно. Именно поэтому это просто аналогия ...
Джошуа Грохов
19

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

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

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

Пол Бим
источник
17

Гипотеза : что для любого детерминированного алгоритма для требуется время .3SUM3SUMΩ(n2)

Это было опровергнуто в 2014 году Алланом Грёнлундом и Сетом Петти, которые дали детерминированный алгоритм, который выполняется за времени [1].O(n2/(logn/loglogn)2/3)

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

Mangara
источник
5
Как в мире они получили этот титул мимо рецензентов?
Дэвид Чжан
17

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

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

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

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

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

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

Андрес Э. Кайседо
источник
9

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

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

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

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

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

Марцио Де Биаси
источник
7

В лекции Мадху Судана * он утверждал, что существует некое убеждение, что существует такое , что через полуопределенное программирование, до доказательства трехбитной теоремы Хостада о PCP.s>1/2PCP1,s[logn,3]P

Действительно, SDP показывает , что дает жесткую оценку сложности таких PCP.PCP1,1/2[logn,3]=P

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

Джо Бебель
источник
1

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

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

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

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

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

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

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

ВЗН
источник
1
Какую гипотезу вы выдвигаете на первый план? Кроме того, сложность схемы кажется очень активной и довольно успешной, например, многочисленные прорывы Россмана; см. авторитетный учебник Юкны для более подробного обзора области.
Андрас Саламон
Есть несколько взаимосвязанных идей, но, например, «грубая» гипотеза о том, что схемы в общем или некотором специальном виде (например, монотонном) могут доказать P против NP или сильные нижние границы ... это никогда не было строго строго формализовано, но циркулирует во многих (старых) документы по теории цепей. это не строго опровергнуто, но сильно пересмотрено с 2020 года. в частности, монотонная схема - это «почти разворот».
vzn
8
Если бы вы указали некоторые конкретные ссылки в качестве поддержки монотонной схемы, это был бы хороший ответ. Но вышесказанное выглядит как бросание большого количества слов в стену и надежда на какую-то палку; у него есть нюанс, но нет четкого тезиса. В моем чтении у меня не сложилось впечатление, что монотонные схемы когда-либо считались особенно мощными.
Андрас Саламон
@ AndrásSalamon: я думаю, что представление представляет выгоду задним числом. То есть после экспоненциальной нижней границы Разборова по монотонным цепям для клики, я думаю, был довольно распространенный оптимизм, что гораздо большие нижние границы схем (такие как ) были "прямо за углом". (Возможно, не так широко распространено, как убеждение, что , но я думаю, что оно достаточно широко распространено, чтобы упоминать его в качестве ответа на этот вопрос.)NPP/polyPneqNP
Джошуа Грохов
@JoshuaGrochow, я согласен, но это сильно отличается от запутанной темы выше. Возможно стоит опубликовать как ответ?
Андрас Саламон