Skip to Content

Кубок Москвы по ЧГК. Гран-При сезона 2010/11 гг. 9 тур. Команда Бориса Гуревича. Вопрос 7

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

Ответ: P=NP.

Комментарий: Одна из основных проблем теории алгоритмов.

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

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

 !