Распространенные ложные убеждения в теоретической информатике

62

РЕДАКТИРОВАТЬ НА 10/12/08:

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

Этот пост вдохновлен тем, что в МО: Примеры распространенных ложных убеждений в математике . Большие списки иногда генерируют огромное количество ответов, качества которых трудно контролировать, но после успеха соответствующего поста в МО я убежден, что было бы полезно перечислить несколько распространенных ложных убеждений в TCS.

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

Каковы некоторые (нетривиальные) примеры распространенных ложных убеждений в теоретической информатике, которые появляются у людей, которые учатся в этой области?

Чтобы быть точным, мы хотим, чтобы примеры отличались от удивительных результатов и противоречивых результатов в TCS; результаты такого рода заставляют людей поверить, но они ИСТИННЫ. Здесь мы просим удивительных примеров, что люди могут подумать, что это правда с первого взгляда, но после более глубокого размышления обнаруживается ошибка внутри.


В качестве примера правильных ответов в списке, этот приходит из области алгоритмов и теории графов:

Для n -node графа G , A k -Станок сепаратор S представляет собой подмножество ребер размера k , где узлы GS может быть разбиение на двух несмежных частей, каждая состоит из не более 3n/4 узлов , У нас есть следующая «лемма»:

Дерево имеет 1-реберный разделитель.

Правильно?

Hsien-Chih Chang 張顯 之
источник
Сообщение было помечено для запроса как CW.
Сянь-Чи Чанг 之 之

Ответы:

59

Это одно из общих для вычислительной геометрии, но повсеместное применение: алгоритмы для реального ОЗУ могут быть перенесены в целочисленное ОЗУ (для целочисленных ограничений задачи) без потери эффективности. Каноническим примером является утверждение «Гауссово исключение выполняется за время . Фактически, неосторожные порядки исключения могут давать целые числа с экспоненциально большим количеством битов .O(n3)

Еще хуже, но, к сожалению, все еще распространено: алгоритмы для реальной оперативной памяти с функцией пола могут быть перенесены в целочисленную оперативную память без потери эффективности. Фактически, пол real-RAM + может решить любую проблему в PSPACE или в #P за полиномиальное количество шагов .

Jeffε
источник
5
Заблуждение об исключении Гаусса очень распространено. Возможно, часть проблемы заключается в том, что мы часто работаем над конечными полями и, поскольку там нет проблем, мы забываем.
Слитон
«После целочисленного исключения Гаусса мы знаем, как найти решение».
Альберт Хендрикс
40

Я только что разрушил еще один миф, которому способствует ответ @ XXYYXX на этот пост :

  • Проблема X является трудной, если есть полиномиальное сокращение времени (или пространства журналов) от всех проблем N P до X.NPNP
  • Предположим гипотезу экспоненциального времени, 3-SAT не имеет субэкспоненциального алгоритма времени. Кроме того , 3-SAT в .NP
  • Таким образом, нет трудных задач X имеет субэкспоненциальные алгоритмы времени. В противном случае алгоритм субэкспоненциального времени для X + сокращение полиномиального времени = алгоритм субэкспоненциального времени для 3-SAT.NP

Но у нас есть субэкспоненциальные алгоритмы времени для некоторых NP-сложных задач.

Hsien-Chih Chang 張顯 之
источник
У меня было такое же впечатление.
Мухаммед Аль-Туркистани
Так что же это говорит нам о гипотезе экспоненциального времени? Или я упустил какой-то недостаток в этом рассуждении?
Михаил Глушенков
2
Существует ошибка в пункте 3. То есть именно то , что я понял в течение длительного времени :)
Сянь-Чжи Чан張顯之
Я не уверен, что не смогу найти ошибку. Является ли это , что с , сокращение не обязательно должен быть полиномом , но что это может быть экспоненциальным во времени, так как обе проблемы были бы в EXPTIME (из - за ETH?)PNP
chazisop
43
Сокращения за полиномиальное время могут изменить размер входных данных на полиномиальную величину. Поэтому, если вы уменьшите экземпляр Q размера n до экземпляра P размера n в квадрате, алгоритм 2 для корневого n для P даст вам только алгоритм 2 к n для Q.
Рассел Импальяццо
29

Ложное убеждение, которое было популяризировано в этом году, и о котором много раз говорят, когда пытаются объяснить всю проблему , поскольку P объясняется как эффективный:PNPP

«Если , то мы можем эффективно решить огромное количество проблем. Если нет, мы не можем»P=NP

Если может быть решена в O ( п г о о г о л р л е х ) , то Р = Н Р . Я не думаю, что кто-то мог бы подумать о запуске этого алгоритма.3SATO(ngoogolplex)P=NP

Если , у нас все еще может быть алгоритм для T S P, который работает в n log ( log n ) , который меньше, чем n 5, для n 2 32 . Большинство людей были бы более чем счастливы, что смогли бы быстро решить проблему T S P для 4 миллиардов городов.PNPTSPnlog(logn)n5n232TSP

chazisop
источник
5
Сообщение в блоге от Lipton хороши: rjlipton.wordpress.com/2009/07/03/is-pnp-an-ill-posed-problem
Сянь-Чжи Чан張顯之
6
«Для каждого алгоритма полиномиального времени, который у вас есть, есть экспоненциальный алгоритм, который я бы предпочел запустить» - Алан Перлис, с помощью Gödel's Lost Letter и P = NP .
Пол GD
25

Это действительно ложное убеждение в математике, но часто встречается в контексте TCS: если случайные величины и Y независимы, то при условии Z они остаются независимыми. (ложь , даже если Z не зависит от обоих X и Y ) .XYZZXY

MCH
источник
2
У вас есть любимый простой пример, который вы бы порекомендовали, чтобы помочь людям быстро понять, почему это ложь?
DW
22
Скажем, и Y являются независимыми и равномерно случайными битами, а Z = X + Y (mod 2). Тогда Z не зависит от X и не зависит от Y , но обусловлен Z , зная, что X раскрывает Y и наоборот. XYZ=X+YZXYZXY
MCH
22

Распределенные вычисления = распределенные высокопроизводительные вычисления (кластеры, сетки, облака, seti @ home, ...).

Распределенные алгоритмы = алгоритмы для этих систем.


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

Типичная проблема заключается в следующем: у нас есть цикл с узлами; узлы помечены уникальные идентификаторы из множества { 1 , 2 , . , , , poly ( n ) } ; узлы являются детерминированными и синхронно обмениваются сообщениями друг с другом. Сколько синхронных раундов связи (в зависимости от n ) необходимо, чтобы найти максимальное независимое множество? Сколько раундов необходимо, чтобы найти независимый набор с по крайней мере n / 1000 узлов? [Ответ на оба эти вопроса точно Θ ( log n{1,2,...,poly(n)}nn/1000 , открытый в 1986–2008 гг.]Θ(logn)

То есть люди часто изучают проблемы, которые являются тривиальными с точки зрения централизованных алгоритмов и имеют очень мало общего с любыми видами суперкомпьютеров или высокопроизводительных вычислений. Дело, конечно, не в ускорении централизованных вычислений за счет использования большего количества процессоров или чего-то подобного.

Цель состоит в том, чтобы построить теорию сложности путем классификации фундаментальных задач графа в соответствии с их вычислительной сложностью (например, сколько требуется синхронных циклов; сколько битов передается). Такие проблемы, как независимые наборы в циклах, могут показаться бессмысленными, но они играют роль, подобную 3-SAT в централизованных вычислениях: очень полезная отправная точка в сокращениях. Для конкретных реальных приложений имеет смысл взглянуть на такие устройства, как маршрутизаторы и коммутаторы в сетях связи, а не на компьютеры в сетях и кластерах.

Эта ложная вера не совсем безобидна. На самом деле, это довольно затрудняет продажу работ, связанных с теорией распределенных алгоритмов, широкой аудитории TCS. Я получил веселые отчеты судей от конференций TCS ...

Юкка Суомела
источник
1
Что касается вычислений, я бы не сказал, что это не ложное убеждение, а скорее устаревшее. Помимо многоядерных процессоров, мелкомасштабные распределенные вычисления были тривиальным случаем высокопроизводительного (по крайней мере из того, что я знаю). С ядрами, являющимися "компьютерами", но на таком небольшом расстоянии, без сети между ними, возникают новые проблемы. Я согласен, однако, что распределенные алгоритмы должны использоваться для m> = 2 узлов.
chazisop
То есть вы просто говорите, что люди путают параллельные вычисления с распределенными?
Сашо Николов
Я думаю, что ваше требование не относится к теоретическим компьютерным ученым, хотя оно может относиться к практическим специалистам без теоретического образования. Как отметил Сашо Николов, люди, работающие в этой области, хорошо знают различия между параллельными и распределенными вычислениями. Проблема, возникающая в кластерах, сетках, облаках и т. Д., Строго зависит от контекста. Например, мы не предполагаем сбои при использовании кластера или облака, но мы делаем для сеток. И так далее.
Массимо Кафаро
Более того, для этого научного сообщества распределенные алгоритмы - это алгоритмы для задач, которые часто встречаются в книгах Нэнси Линч, Хагит Аттия, Дженнифер Уэлч и Джерарда Тела. И, как таковые, эти алгоритмы предназначены для конкретной теоретической модели распределенных вычислений и анализируются по мере необходимости с точки зрения используемых ресурсов (сложность времени, сложность сообщений, сложность битов, количество циклов и т. Д.).
Массимо Кафаро
@MassimoCafaro: Конечно, люди, которые работают в области распределенных вычислений, знают, что такое распределенные вычисления. Однако мой опыт показывает, что теоретические компьютерные ученые вообще не знают, что такое распределенные вычисления.
Юкка Суомела
20

Элементарный, но распространенный, когда мы впервые имеем дело с асимптотическими обозначениями. Рассмотрим следующее «доказательство» рекуррентного соотношения и T ( 1 ) = 1 :T(n)=2T(n/2)+O(nlogn)T(1)=1

Докажем по индукции. Для базового случая это верно для . Предположим, что соотношение выполняется для всех чисел, меньших, чем n ,n=1n

T(n)=2T(n/2)+O(nlogn)=2O(n/2logn/2)+O(nlogn)=O(nlogn/2)+O(nlogn)=O(nlogn)

КЭД (это?)

Сянь-Чжи Чан 張顯 之
источник
16
Я видел, как студенты делают это. Это одна из ловушек злоупотребления обозначениями и написания а не f ( x ) O ( g ( x ) ) . f(x)=O(g(x))f(x)O(g(x))
Аарон Рот
Я видел, как исследователи в теоретической информатике тоже делают варианты этой ошибки;)
Джереми
12

До недавнего времени я считал , что каждый мульти-лента машина Тьюринга , которая работает во времени Т ( п ) можно моделировать с помощью двух ленточных рассеянной Тьюринга machinne M O во времени O ( T ( п ) войти Т ( п ) ) в следующем смысл:MT(n)MoO(T(n)logT(n))

  • движение голов зависит только от длины вводаMo
  • для всех входов одинаковой длины останавливается в одно и то же время (что составляет Θ ( T ( n ) log T ( n ) ) ).MoΘ(T(n)logT(n))

(см. этот пост Rjlipton, например)

Хорошо, вторая линия не имеет места в общем случае , если . Нам нужна полностью конструируемая во времени функция порядка Θ ( T ( n ) log T ( n ) ) (см. Этот вопрос для определения (полностью) конструируемых во времени функций) или нам нужно разрешить M o работать в течение бесконечного времени (мы позволяем M o работать после того, как он достигнет состояния принятия вEXPTIMENEXPTIMEΘ(T(n)logT(n))MoMo времени). Проблема в том, что для общего времени : T : NN мы не можем «измерить» Θ ( T ( n ) log T ( n ) ) шагов за время O ( T ( n ) log T ( n ) ), если только E X P - T I M EO(T(n)logT(n))T:NNΘ(T(n)logT(n))O(T(n)logT(n)) .EXPTIME=NEXPTIME

Доказательство этого утверждения очень похоже на доказательство в ответе Q1 здесь , поэтому мы приведем только ключевые идеи.

Возьмем произвольную задачу , L { 0 , 1 } . Тогда существует k N , st L может быть решена с помощью NDTM M за 2 n k шагов. Для простоты можно предположить, что на каждом шаге M переходит в самое большее два разных состояния. Далее определим функцию f ( n ) = { ( 8 n + 2LNEXPTIMEL{0,1}kNLM2nkM Можно доказать, чтоfявляется конструируемой во времени.

f(n)={(8n+2)2if (first logn+1k bits of bin(n))L8n+1else
f

Теперь предположим, что некоторая забывающая машина Тьюринга работает за время . Тогда g вполне конструируема по времени.g(n)=Θ(f(n)logf(n))g

Теперь следующий алгоритм решает :L

  • на входе пусть n будет числом с двоичным представлением x 00 0 ( | x | k - 1 ноль). Отсюда следует, что x = ( first k xnx000|x|k1.x=(first logn+1k bits of bin(n))
  • вычислить за время g ( n ) . Если г ( п ) достаточно велико, то х L , то х л . (это работает только для достаточно большого п . Насколько большой зависит от г. )g(n)g(n)g(n)xLxLng

Этот алгоритм работает в экспоненциальное время и решает . Так как L N Е Х Р - Т Я М Е произвольно, Е Х Р - Т Я М Е = Н Е Х Р - Т Я М Е .LLNEXPTIMEEXPTIME=NEXPTIME

Дэвид Г
источник
11

Вот мои два цента:

Класс сложности , рандомизированное логарифмическое пространство , определяется как аналог R P , то есть проблемы решения, которые могут быть решены с помощью недетерминированной логарифмической машины M , гдеRLRPM

  • для положительного , например, принимает с вероятностью по крайней мере 1 / 2 ;M1/2
  • для отрицательного случая отклоняет с вероятностью 1 .M1

Кроме того, машина всегда останавливается.

Это определение правильно? (Нет)

Сянь-Чжи Чан 張顯 之
источник
9

еграмм1Nе(N)грамм(N)е(N+1)знак равноо(грамм(N))

NTяMЕ(е(N))NTяMЕ(грамм(N))

NTяMЕ(грамм(N))-NTяMЕ(е(N))е(N)грамм(N)NTяMЕ(е(N))NTяMЕ(грамм(N))е,грамме(N+1)знак равноо(грамм(N))е(N)грамм(N)

NTяMЕ(е(N))NTяMЕ(грамм(N))е,грамме(N+1)знак равноо(грамм(N))

е(N)знак равно{N+1N странный(N+1)3еще
грамм(N)знак равное(N+1)2еграмме(N+1)знак равноо(грамм(N))LNTяMЕ((N+1)3)-NTяMЕ((N+1)2){0,1}
L1знак равно{0Икс10Икс2...0ИксN;  Икс1Икс2...ИксNL},

L1NTяMЕ(е(N))L1NTяMЕ(грамм(N))LNTяMЕ((N+1)2)L1NTяMЕ(е(N))-NTяMЕ(грамм(N))

Дэвид Г
источник
9

NпUпNпрпUпNпрUпNпзнак равноUпNпрппромяsеUп

UпLИксLUSUSUпсоNпUS

Джошуа Грохов
источник
что означает «семантическое свойство, которое во всех случаях»?
T ....
1
@ 777: семантическое свойство означает: не может быть проверено непосредственно из структуры (или синтаксиса) самого TM / алгоритма. Эта фраза имеет больше смысла, если вы продолжите ее после запятой, то есть: свойство, которое: «во всех случаях есть не более одного свидетеля»
Джошуа
-2

μИкс{Иксзнак равноμ}

user1596990
источник
9
Это, конечно, общая ложная вера среди студентов теоретической информатики, но это не так часто среди теоретической информатики исследователей .
Джефф