Примеры педантизма в ТКС

Ларри Вассерман недавно опубликовал пост, где рассказывает о «полиции p-значения». Он делает интересное замечание (все выделено мной) (предпосылка, которую я добавил курсивом, и его ответ под ним):

Наиболее распространенная жалоба состоит в том, что физики и журналисты неправильно объясняют значение p-значения. Например, если значение p равно 0,000001, мы увидим такие утверждения, как «с вероятностью 99,9999%, что сигнал настоящий». Затем мы чувствуем необходимость исправить утверждение: если эффекта нет, то вероятность чего-либо или более экстремальный 0,000001.

Справедливо. Но действительно ли это имеет значение? Общая картина такова: доказательства этого эффекта подавляющи. Действительно ли имеет значение, если формулировка немного вводит в заблуждение? Я думаю, что мы укрепляем наш имидж как педанты, если будем жаловаться на это.

Что заставило меня задуматься -

Есть ли хорошие примеры педантизма в ТКС? Такой пример будет состоять из

• Утверждение, которое обычно делается в популярной прессе
• Стандартное исправление, на котором настаивают люди
• Правильная «большая картина», которую претензия запечатлела, даже будучи неточной.

где утверждение математически неверно, но «морально правильно», а исправление технически правильно, но не меняет интуитивное понимание.

Чтобы привести вещи в порядок, мой пример будет:

• Требование - NP-полные проблемы требуют экспоненциального времени для решения
• Исправление - Нет, на самом деле мы просто не знаем, можно ли их решить за полиномиальное время
• Большая картина - NP-полные проблемы трудны

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

Хм, сложно даже вспомнить примеры заявлений о TCS, которые попадают в популярную прессу.

Одна вещь, которую я иногда видел, это утверждение, что факторинг сложен с точки зрения NP при объяснении криптографии. Это связано с менее безобидной ошибкой утверждения о том, что квантовые компьютеры могут решать сложные проблемы NP, но ограниченные контекстом криптографии, это относительно легкая ошибка. Дело в том, что мы (пользователи криптографии), похоже, считаем, что не существует эффективного алгоритма для решения проблемы. Конкретные предположения, которые мы используем, чтобы оправдать это утверждение, помимо сути.

• утверждение прессы: о вещах, которые растут "в геометрической прогрессии", то есть претензии O (k ^ n)

• на самом деле верно: часто постоянная мощность O (n ^ k)

• большая картина: она растет достаточно быстро, все в порядке

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

Для примера возьмите любую статью в прессе об алгоритме эллипсоида с момента его обнаружения (отличный рассказ об этой истории: http://www.springerlink.com/content/vh32532p5048062u/ ). Пресса утверждала, что это новое великое математическое открытие повлияет на жизнь каждого, решит TSP (что они нашли особенно ироничным, учитывая, как мало было путешествующих продавцов в СССР!), Перевернет крипто вверх ногами и т. Д.

Затем есть AKS, который в некоторых отчетах даже подразумевал решение факторинга или, по крайней мере, инновацию, которая изменила отрасль.

Я уверен, что есть еще много примеров.

• На самом деле верно: полиномиальное время не означает практическое! Показательный пример: алгоритм эллипсоида, выборка из выпуклых многомерных тел. Экспоненциальное время в худшем случае не означает непрактичное. Показательный пример: симплексный алгоритм. Когда новый алгоритм является просто первым детерминированным многопоточным алгоритмом для задачи, это имеет еще меньшее отношение к практике.

• $\log^5 n$

Популярная пресса часто создает впечатление, что основной, если не единственной причиной того, что компьютеры преуспевают во все большем и большем количестве задач (избиение Каспарова в шахматах, избиение Дженнингса в «Опасности» и т. Д.), Является увеличение вычислительной мощности. Алгоритмические достижения, как правило, не так уж важны.

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

Скотт Ааронсон, хотя и является главным авторитетом, похоже, регулярно привлекает СМИ к ответственности за неправильное расчесывание волос. например, его недавняя колонка в статье « Нью-Йорк Таймс » «Квантовые вычисления обещают новые идеи, а не только супермашины» [курсив добавлен]

Изо всех сил пытаясь превратить эту математику в удобные для газет метафоры, большинство популярных авторов описывают квантовый компьютер как магическую машину, которая может обрабатывать каждый возможный ответ параллельно, а не пробовать их по одному. Возможно, это могло бы быть сделано потому, что в отличие от современных компьютеров, которые манипулируют битами, квантовый компьютер будет манипулировать квантовыми битами или кубитами, которые могут быть равны 0 и 1 одновременно.

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

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

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