Интересные результаты в TCS, которые легко объяснить программистам без технического образования

13

Предположим, вы встречаетесь с программистами, которые прошли некоторые профессиональные курсы по программированию (или думали сами), но не изучали математику университетского уровня.

Чтобы показать им всю прелесть TCS, я хотел бы собрать некоторые хорошие результаты / открытые вопросы, поступающие от TCS, которые легко объяснить.

Хороший кандидат для этой цели (ИМХО) покажет, что проблема остановки не решаема. Другой будет показывать нижнюю границу времени сортировки на основе сравнения (хотя это немного отталкивает от того, что, как я ожидаю, они поймут).

Я также могу использовать идеи из объяснения проблемы P = NP для 10-летних , предполагая, что некоторые из них не знакомы с ней.

Итак, вопросы должны быть:

(0. Красиво)

  1. Объясняется с (максимум) математикой средней школы.
  2. (желательно) не достаточно тривиально для показа на курсах профессионального программирования (для C ++ / Java / Web / и т. д.).
RB
источник
Разве это не полностью основано на мнении?
Дэвид Ричерби
6
Я думаю, что это хороший вопрос. Подобные, плодотворные вопросы по mathoverflow: mathoverflow.net/questions/47214/… . mathoverflow.net/questions/56547/applications-of-matmatics .
usul
1
также несколько похоже на «описание обеденного стола TCS» . imho, мой фаворит - существование жестких функций, доказанных Шенноном, но почти нет конструктивных доказательств каких-либо конкретных жестких функций после более чем 1/2 века ....
vzn
1
О существовании quines всегда весело упоминать программистам.
Денис
2
может быть, это должно быть сообщество вики?
Суреш Венкат

Ответы:

9

В дополнение к проблеме остановки, я предлагаю обсудить:

Теорема Райса. Некоторые объяснения в Википедии немного жаргонны, но, как правило, это не сложная теорема или доказательство, чтобы понять что-то другое; он имеет большое значение для реальных концепций, таких как антивирусное программное обеспечение. Доказательство примерно такое же сложное, как и доказательство проблемы остановки (и фактически зависит от неразрешимости проблемы остановки). По сути, просто поймите, что «вычислимая функция» - это машина Тьюринга или компьютерная программа.

Филип Уайт
источник
4
Я не думаю, что сложность факторинга, как известно, подразумевает безопасность RSA.
Сашо Николов
1
Это был значительный пробел в моих знаниях о крипто. Спасибо что подметил это; Я отредактировал свой ответ.
Филипп Уайт
1
Если вам интересно, вы можете посмотреть на это: crypto.stanford.edu/~dabo/papers/no_rsa_red.pdf . Тем не менее, ваш пример был хорошим, даже если детали были неверны. Для Диффи-Хеллмана эквивалентность дискретному журналу известна для многих циклических групп, в том числе, например, используемых в практических приложениях: citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.78.3339 . Кроме того, Диффи-Хеллмана на самом деле легче объяснить, чем RSA, IMO
Сашо Николов
5

Я думаю, что - независимо от вопроса P против NP - теорема Кука-Левина (и связанное с ней понятие NP-полноты) является еще одним очень хорошим кандидатом; если у вас есть (эффективный) решатель для SAT, то у вас есть (эффективный) решатель для любой проблемы в NP .... и вы можете получить нечто удивительное, по крайней мере для меня:

  • aИкс12+бИкс2+сзнак равно0
  • решить судоку;
  • нахождение гамильтонова пути в графе;
  • решение экземпляра подмножества суммы;
  • и много других (реальных) проблем ...

в некотором смысле "эквивалентные проблемы"; так что если ваш босс попросит вас создать программу для упаковки коробок в контейнер ... вы можете дать ему решатель Сапер ... :-)

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

Забавный и интересный пример - неразрешимость проблемы тайлов тайлов Ванга. Результат непосредственно следует из неразрешимости проблемы Остановки простым моделированием машин Тьюринга с использованием плиток Ванга. Интересно, что неразрешимость проблемы листов для плиток Ванга привела к прекрасному результату, что есть наборы плиток, которые разбивают плоскость только на апериодику.

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

NпNп

Мухаммед Аль-Туркистани
источник
3

избранное, собранное здесь и в другом месте

ВЗН
источник
2
также еще один очень важный алгоритм с некоторыми глубокими углами TCS: Pagerank
vzn