РЕДАКТИРОВАТЬ НА 10/12/08:
Я постараюсь изменить вопрос, чтобы он мог заинтересовать больше людей поделиться своим мнением. Нам нужен ваш вклад!
Этот пост вдохновлен тем, что в МО: Примеры распространенных ложных убеждений в математике . Большие списки иногда генерируют огромное количество ответов, качества которых трудно контролировать, но после успеха соответствующего поста в МО я убежден, что было бы полезно перечислить несколько распространенных ложных убеждений в TCS.
Тем не менее, поскольку сайт предназначен для ответов на вопросы исследовательского уровня, таких примеров, как обозначающих неполиномиальное время, не должно быть в списке. Между тем, нам нужны примеры, которые могут быть не сложными, но, не вдаваясь в детали, они также выглядят разумными. Мы хотим, чтобы примеры были обучающими, и обычно появляются при первом изучении предмета.
Каковы некоторые (нетривиальные) примеры распространенных ложных убеждений в теоретической информатике, которые появляются у людей, которые учатся в этой области?
Чтобы быть точным, мы хотим, чтобы примеры отличались от удивительных результатов и противоречивых результатов в TCS; результаты такого рода заставляют людей поверить, но они ИСТИННЫ. Здесь мы просим удивительных примеров, что люди могут подумать, что это правда с первого взгляда, но после более глубокого размышления обнаруживается ошибка внутри.
В качестве примера правильных ответов в списке, этот приходит из области алгоритмов и теории графов:
Для -node графа , A -Станок сепаратор представляет собой подмножество ребер размера , где узлы может быть разбиение на двух несмежных частей, каждая состоит из не более узлов , У нас есть следующая «лемма»:
Дерево имеет 1-реберный разделитель.
Правильно?
Ответы:
Это одно из общих для вычислительной геометрии, но повсеместное применение: алгоритмы для реального ОЗУ могут быть перенесены в целочисленное ОЗУ (для целочисленных ограничений задачи) без потери эффективности. Каноническим примером является утверждение «Гауссово исключение выполняется за время . Фактически, неосторожные порядки исключения могут давать целые числа с экспоненциально большим количеством битов .O(n3)
Еще хуже, но, к сожалению, все еще распространено: алгоритмы для реальной оперативной памяти с функцией пола могут быть перенесены в целочисленную оперативную память без потери эффективности. Фактически, пол real-RAM + может решить любую проблему в PSPACE или в #P за полиномиальное количество шагов .
источник
Я только что разрушил еще один миф, которому способствует ответ @ XXYYXX на этот пост :
Но у нас есть субэкспоненциальные алгоритмы времени для некоторых NP-сложных задач.
источник
Ложное убеждение, которое было популяризировано в этом году, и о котором много раз говорят, когда пытаются объяснить всю проблему , поскольку P объясняется как эффективный:п≠ Nп п
«Если , то мы можем эффективно решить огромное количество проблем. Если нет, мы не можем»п= Nп
Если может быть решена в O ( п г о о г о л р л е х ) , то Р = Н Р . Я не думаю, что кто-то мог бы подумать о запуске этого алгоритма.3 SА Т O ( nграммо о гО л р л е х) п= Nп
Если , у нас все еще может быть алгоритм для T S P, который работает в n log ( log n ) , который меньше, чем n 5, для n ≤ 2 32 . Большинство людей были бы более чем счастливы, что смогли бы быстро решить проблему T S P для 4 миллиардов городов.п≠ Nп TSп Nжурнал( журналн ) N5 n ≤ 232 TSп
источник
Это действительно ложное убеждение в математике, но часто встречается в контексте TCS: если случайные величины и Y независимы, то при условии Z они остаются независимыми. (ложь , даже если Z не зависит от обоих X и Y ) .Икс Y Z Z Икс Y
источник
Распределенные вычисления = распределенные высокопроизводительные вычисления (кластеры, сетки, облака, seti @ home, ...).
Распределенные алгоритмы = алгоритмы для этих систем.
Спойлер: Если это не похоже на «ложное убеждение», я предлагаю вам взглянуть на такие конференции, как PODC и DISC, и посмотреть, какую работу люди действительно выполняют, изучая теоретические аспекты распределенных вычислений.
Типичная проблема заключается в следующем: у нас есть цикл с узлами; узлы помечены уникальные идентификаторы из множества { 1 , 2 , . , , , poly ( n ) } ; узлы являются детерминированными и синхронно обмениваются сообщениями друг с другом. Сколько синхронных раундов связи (в зависимости от n ) необходимо, чтобы найти максимальное независимое множество? Сколько раундов необходимо, чтобы найти независимый набор с по крайней мере n / 1000 узлов? [Ответ на оба эти вопроса точно Θ ( log ∗N { 1 , 2 , . , , , poly ( n ) } N н / 1000 , открытый в 1986–2008 гг.]Θ(log∗н )
То есть люди часто изучают проблемы, которые являются тривиальными с точки зрения централизованных алгоритмов и имеют очень мало общего с любыми видами суперкомпьютеров или высокопроизводительных вычислений. Дело, конечно, не в ускорении централизованных вычислений за счет использования большего количества процессоров или чего-то подобного.
Цель состоит в том, чтобы построить теорию сложности путем классификации фундаментальных задач графа в соответствии с их вычислительной сложностью (например, сколько требуется синхронных циклов; сколько битов передается). Такие проблемы, как независимые наборы в циклах, могут показаться бессмысленными, но они играют роль, подобную 3-SAT в централизованных вычислениях: очень полезная отправная точка в сокращениях. Для конкретных реальных приложений имеет смысл взглянуть на такие устройства, как маршрутизаторы и коммутаторы в сетях связи, а не на компьютеры в сетях и кластерах.
Эта ложная вера не совсем безобидна. На самом деле, это довольно затрудняет продажу работ, связанных с теорией распределенных алгоритмов, широкой аудитории TCS. Я получил веселые отчеты судей от конференций TCS ...
источник
Элементарный, но распространенный, когда мы впервые имеем дело с асимптотическими обозначениями. Рассмотрим следующее «доказательство» рекуррентного соотношения и T ( 1 ) = 1 :T( n ) =2T( n / 2 ) + O (nlogн ) T( 1 ) = 1
Докажем по индукции. Для базового случая это верно для . Предположим, что соотношение выполняется для всех чисел, меньших, чем n ,n = 1 N
КЭД (это?)
источник
До недавнего времени я считал , что каждый мульти-лента машина Тьюринга , которая работает во времени Т ( п ) можно моделировать с помощью двух ленточных рассеянной Тьюринга machinne M O во времени O ( T ( п ) войти Т ( п ) ) в следующем смысл:M T( н ) Mо O ( T( n ) журналT( н ) )
(см. этот пост Rjlipton, например)
Хорошо, вторая линия не имеет места в общем случае , если . Нам нужна полностью конструируемая во времени функция порядка Θ ( T ( n ) log T ( n ) ) (см. Этот вопрос для определения (полностью) конструируемых во времени функций) или нам нужно разрешить M o работать в течение бесконечного времени (мы позволяем M o работать после того, как он достигнет состояния принятия вЕИксп- ТяMЕ≠ NЕИксп- ТяMЕ Θ ( Т( n ) журналT( н ) ) Mо Mо времени). Проблема в том, что для общего времени : T : N → N мы не можем «измерить» Θ ( T ( n ) log T ( n ) ) шагов за время O ( T ( n ) log T ( n ) ), если только E X P - T I M EO ( T( n ) журналT( н ) ) T: N → N Θ ( Т( n ) журналT( н ) ) O ( T( n ) журналT( н ) ) .ЕИксп- ТяMЕ= NЕИксп- ТяMЕ
Доказательство этого утверждения очень похоже на доказательство в ответе Q1 здесь , поэтому мы приведем только ключевые идеи.
Возьмем произвольную задачу , L ⊆ { 0 , 1 } ∗ . Тогда существует k ∈ N , st L может быть решена с помощью NDTM M за 2 n k шагов. Для простоты можно предположить, что на каждом шаге M переходит в самое большее два разных состояния. Далее определим функцию f ( n ) = { ( 8 n + 2L ∈ NЕИксп- ТяMЕ L ⊆ { 0 , 1 }* k ∈ N L M 2NК M
Можно доказать, чтоfявляется конструируемой во времени.
Теперь предположим, что некоторая забывающая машина Тьюринга работает за время . Тогда g вполне конструируема по времени.грамм( n ) = Θ ( f( н )журнале( н ) ) грамм
Теперь следующий алгоритм решает :L
Этот алгоритм работает в экспоненциальное время и решает . Так как L ∈ N Е Х Р - Т Я М Е произвольно, Е Х Р - Т Я М Е = Н Е Х Р - Т Я М Е .L L ∈ NЕИксп- ТяMЕ ЕИксп- ТяMЕ= NЕИксп- ТяMЕ
источник
Вот мои два цента:
Класс сложности , рандомизированное логарифмическое пространство , определяется как аналог R P , то есть проблемы решения, которые могут быть решены с помощью недетерминированной логарифмической машины M , гдеR L R P M
Кроме того, машина всегда останавливается.
Это определение правильно? (Нет)
источник
источник
источник
источник