Противоречивые результаты для студентов

14

Я ищу примеры результатов, которые идут вразрез с интуицией людей для общей аудитории. Результаты, которые, если спросить у неэкспертов «что говорит ваша интуиция?», Почти все ошиблись бы. Заявление о результатах должно быть легко объяснимо для студентов в CS / математике. Я в основном ищу результаты в области компьютерных наук.

Каковы наиболее противоречивые / неожиданные результаты (общего интереса) в вашем регионе?

анонимное
источник
7
тесно связаны: cstheory.stackexchange.com/q/276/4896 и cstheory.stackexchange.com/q/2802/4896
Сашо Николов
1
Вторая ссылка Сашо является дубликатом, не так ли?
Гек Беннетт
Похоже, но не то же самое. Я ищу результаты, которые интересны и нелогичны для студентов бакалавриата по математике, а не для исследователей. Например, IP = PSPACE не будет хорошим ответом.
Аноним
4
Для достаточно больших входных размеров первичность всегда может быть определена за меньшее время, чем самый быстрый из известных способов получить незначительный шанс факторизации модуля RSA.

Ответы:

25

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

Вот несколько идей, которые можно разработать для завершения примеров:

  1. Есть поверхность, которая имеет только одну сторону .
  2. Кривая может заполнить весь квадрат .
  3. Есть кривые постоянной ширины, кроме круга.
  4. Можно раскрасить плоскость тремя цветами таким образом, чтобы каждая точка границы была три-границей .

Если вы можете положиться на немного математических знаний, вы можете сделать больше:

  1. Нечетных чисел столько же, сколько и натуральных.
  2. Существует непрерывная и нигде не дифференцируемая функция .
  3. Есть функция которая разрывна на всех рациональных числах и дифференцируема на всех иррациональных числах.е:рр
  4. Банаха-Тарского «парадокс» .

Для программистов вы можете попробовать:

  1. В невозможные функционалы : есть программа , которая принимает предикат p : stream → bool, где streamявляется типом данных бесконечных двоичных последовательностей, и возвращает trueтогда и только тогда , когда p αявляется trueдля всех потоков α(это несчетное множество), и в falseпротивном случае.

  2. Можно играть в покер по телефону в доверенном способом , который предотвращает обман.

  3. Группа людей может рассчитать свою среднюю зарплату, и никто не узнает зарплату другого человека.

  4. Существует программа, которая создает двоичное дерево T со следующими свойствами:

    • дерево бесконечноT
    • нет программы, которая отслеживает бесконечный путь в T
Андрей Бауэр
источник
парадокс Банаха-Тарского (и связанные с ним парадоксы) связан с понятиями (и манипуляциями) бесконечности, что даже профессиональные математики могут ошибаться (или не соглашаться по этому поводу) :)
Никос М.
4
Согласен, но это своего рода вопиющая теорема, которая вызывает интерес людей. Это дает им толчок и заставляет их сомневаться в своих собственных представлениях о бесконечности.
Андрей Бауэр
17

Одна идея - это нечто простое из потоковых алгоритмов . Вероятно, лучшим кандидатом является алгоритм большинства. Скажем, вы видите поток чисел , один за другим, и вы знаете, что одно число встречается более половины времени, но вы не знаете, какое из них. Как вы можете найти номер большинства, если вы помните только два числа одновременноs1,...,sN ? Ответ - алгоритм Мисры-Гриса.

На каждом временном шаге вы сохраняете число из потока и частотомер f . В начале вы устанавливаете x на первое число потока и инициализируете частоту f равной 1. Затем, когда вы видите новое число s i , вы проверяете, если x = s i . Если x = s i , увеличьте f до f + 1 , в противном случае уменьшите f до f - 1 . Если f = 0 , установите x в s iИксеИксеsяИксзнак равноsяИксзнак равноsяее+1ее-1езнак равно0Иксsяи обратно к 1 . После последнего элемента потока, если существовал мажоритарный элемент, он будет равен xе1Икс .

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

Чтобы сделать ответ самодостаточным, вот игра. Предположим, вы хотите убедить своего дальтоника в том, что вы можете отличить красный от зеленого. У вашего друга две колоды карт, и он знает, что одна колода зеленая, а другая красная. Он делает следующее, не видя его: с вероятностью 1/2 он берет одну карту из каждой колоды, с вероятностью 1/4 он берет две карты из левой колоды, а с вероятностью 1/4 он берет две карты из правой колоды , Затем он показывает вам карточки и спрашивает, имеют ли они одинаковый цвет. Если вы не дальтоник, вы, конечно, можете ответить правильно каждый раз. Если вы дальтоник, вы потерпите неудачу с вероятностью 1/2. Так что теперь, если в игру играют 10 раз, вероятность того, что вы сможете выиграть каждый раз, будучи дальтоником, чрезвычайно мала.

Кикер в том, что если ваш друг знал две колоды карт двух разных цветов, но не знал, какая из них красная, а какая зеленая, он все равно не узнает в конце этого! Итак, в заключение:

  1. В доказательствах есть место случайности.
  2. Вы можете убедить кого-то, что вы что-то знаете, не давая им никакой информации об этом.
Сашо Николов
источник
3
Помимо Misra-Gries, я также думаю, что отбор проб из резервуара прост, но хорош.
Джухо
1
@ Джухо, я согласен. Популярный вопрос для интервью :)
Сашо Николов
13

Объем единичной сферы размерности сначала увеличивается с ростом n ( 2 , π , 4 π / 3 , ), но начинает уменьшаться при n = 6 и в конечном итоге сходится к 0 при n .nn2,π,4π/3,n=60n

Денис
источник
1
И причиной этого является произвольное решение рассмотреть сферы единичного радиуса, а не другой параметр длины. В частности, объемы сфер диаметром 1 уменьшаются с самого начала.
Эмиль Йержабек 3.0
Есть много смежных, нелогичных фактов о геометрии в больших измерениях. Например, возьмите единичный гиперкуб и нарисуйте сферу, касающуюся всех сторон. Как далеко угол гиперкуба от сферы? (Ответ: при увеличении размера он расходится до . Радиус сферы равен 0,5 , но расстояние от центра до угла куба составляет 0,5 0,5 .)0,5N
усул
10

Противоречивым результатом теории сложности является теорема PCP:

Неофициально заявляет, что для каждой задачи A существует эффективная рандомизированная машина Тьюринга, которая может проверять правильность доказательства (доказательство принадлежности к A ), используя логарифмическое число случайных битов и считывая только постоянное количество битов из доказательства. Константа может быть уменьшена до 3 бит. Следовательно, рандомизированный верификатор должен считывать только три бита из объявленного доказательства.NPAA

Мухаммед Аль-Туркистани
источник
Какая ссылка для "может быть уменьшена до 3 бит"?
Райан
2
Это известно как 3-битная (или 3-х запросная) теорема Хостада о PCP, и она требует пожертвования совершенной полнотой
Джо Бебель,
1
Здесь вы найдете дополнительную информацию и ссылку на статью Хостада: people.csail.mit.edu/madhu/papers/1998/glst.pdf
Мухаммед Аль-Туркистани
6
@JoeBebel На самом деле есть 3-битные верификаторы с идеальной полнотой. Верификатор Hastad является «линейным»: он отбирает три бита и принимает их XOR. Для такого верификатора вам нужно пожертвовать совершенной полнотой. Кстати, есть PCP доказательства, которые читают только два бита (опять же обязательно без полной полноты). Например, см. Мой ответ здесь cstheory.stackexchange.com/a/20549/4896
Сашо Николов
9

Одна вещь, которая оказывается нелогичной для студентов бакалавриата CS, заключается в том, что можно выбрать статистику порядка из несортированного массива из n элементов за O ( n ) время. Все студенты думают, что они должны сначала обязательно отсортировать массив (за O ( n l g n ) время).inO(n)O(n lg n)

Массимо Кафаро
источник
7

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

также потребовалось около ¾ века, чтобы доказать, что целочисленные диофантовы уравнения неразрешимы, 10-я проблема Гильбертса . это противоречит здравому смыслу в том смысле, что всегда было известно, что теория чисел была чрезвычайно трудной, но концепция, что некоторые конкретные / идентифицируемые проблемы в ней на самом деле «невозможно решить», была для некоторых почти шокирующей. неразрешимость продолжает оставаться серьезной проблемой в математике / TCS, даже несмотря на то, что у нас десятилетия экспоненциального роста аппаратного обеспечения из-за закона Мура и все же массивных суперкомпьютеров, которые в некотором смысле все еще «бессильны против него». некоторые аспекты неожиданности неразрешимости можно найти в книге Клейна « Математика, потеря уверенности ».

ВЗН
источник
2
Бумага Тьюринга была не очень абстрактной / технической. Это на самом деле довольно просто и доступно.
Джефф
1
хорошо, может быть для вас, сейчас, но сколько студентов вы знаете, кто может следить за всей статьей? ли вы следовать за ним как студент? почему полное фактическое содержание не охвачено в старших классах? почему была написана целая книга, анализирующая эту единственную статью? как насчет частей, которые предвосхищают концепции, не обнаруженные до десятилетий спустя, такие как переписка Карри-Ховарда , языки программирования высокого уровня и т. д.?
vzn
3
Тем не менее, «длинные, высокотехнологичные статьи / аргументы, понятные только ведущим математикам того времени» не являются точными по отношению к статье Тьюринга, которая на несколько порядков более доступна, чем статьи Годеля. Этот ответ полон не sequitirs. Я не могу понять, какое отношение финитизм имеет к программе Гильберта (я уверен, что он не был бы финитистом). То, что закон Мура имеет отношение к неразрешимости, также является загадкой для меня. Вы действительно ожидаете, что экспоненциально более быстрое оборудование решит неразрешимые проблемы?
Сашо Николов
3
почему полное фактическое содержание не охвачено в старших классах? - Недостаточно времени.
Джефф
1
Честно говоря, я не знал о финитизме Гильберта. Я был знаком только с современными и гораздо более строгими понятиями финитизма. Было бы лучше, если бы вы написали хороший ответ, а не приглашали людей в чат, но я почему-то сомневаюсь, что вы последуете этому совету.
Сашо Николов
6

Это кажется очевидным, но из личного опыта идея о том, что вы можете оценить медиану коллекции предметов, используя постоянное количество операций, немного шокирует. И если это кажется слишком техническим, вы всегда можете преобразовать его в утверждение о проведении выборов (вам нужно 1300 человек, чтобы получить выборку с ошибкой 3%, независимо от численности населения).

С этим связан парадокс дня рождения, конечно.

Суреш Венкат
источник
5

Возможно, хорошим примером (непосредственно не связанным с вычислительной сложностью) является универсальность Тьюринга простых вычислительных моделей.

Например, правило 110 эффективно (слабо) универсально:

Учитывая (бесконечный) массив из 0-1 (бело-черных) ячеек, правильно инициализированных и простых правил замещения:

enter image description here

у нас есть «рабочий компьютер»! :-)

Для определения «слабых» и «эффективных», а также для других примеров простых универсальных машин Тьюринга посмотрите: Turlough Neary, Damien Woods; Сложность маленьких универсальных машин Тьюринга: обзор .

Другим удивительным примером является полнота по Тьюрингу «языка программирования» FRACTRAN :

  • «Программа» представляет собой список фракций: (п1/Q1,п2/Q2,,,,,пN/QN);
  • учитывая вход N найти первый Qя это делит N и заменить NNпяQя;
  • повторять предыдущий шаг, пока нет Qя водоразделы N,

С подходящей кодировкой ввода NFRACTRAN может моделировать любую машину Тьюринга.

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

Марцио де Биаси
источник
3

Несколько хороших кандидатов с моей головы:

  • Каждый NFA имеет эквивалентный DFA

  • Существует конечное поле размера п или пя где яN и я>0,

  • Криптография с открытым ключом

    • Вызов функции с зашифрованными аргументами и получение желаемого результата без раскрытия информации о ваших входных данных

    • RSA-шифрование

  • Коды Рида-Соломона

  • счетности

    • |N|знак равно|Z|знак равно|N×N|знак равно|Q|

    • Набор элементов в языке {0,1}* исчисляется, но р неисчислимо (диагонализация Кантора)

    • Теорема Кантора: |S|<|п(S)|

  • На более философском уровне меня поразило, что машины Тьюринга точно определяют вычисления

Бхарадвад Рамачандран
источник