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

P=NP.

Комментарии: Одна из основных проблем теории алгоритмов.
Редакторы благодарят Бориса Гуревича, Михаила Иванова, Дмитрия Борока, Максима Богатова, Антона Бочкарёва и Наталию Новыш за ценные замечания или же их отсутствие.

Автор: Олег Христенко (Москва)

Источник: История, рассказанная автору вопроса.

Чемпионат: Кубок Москвы по ЧГК. Гран-При сезона 2010/11 гг.

Тур: 9 тур. Команда Бориса Гуревича

Номер: Вопрос 7

Показать как json