Челябинский математик решил одну из задач, тысячелетия, на миллион долларов...

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

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

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

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

+1
Я там даже преподавал 5 лет назад.

При подборе пароля по хэшу обычно считается прямая функция, а не обратная. Кроме тех случаев, когда сама функция неудачна. То есть по сути уже доказано, что N <> NP, но пока только на конкретных примерах. Нет только универсального математического определения этого. Поэтому новость о том что они равны автоматически фейк )

Добавлено в 21:07
брр... ну в смысле p <> np, у прикладников-программистов это просто не так называется )

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

Не совсем так. Она должна по обратной функции иметь достаточно много корней, чтобы пользоваться ей было бессмысленно. Ну не быстрей, чем обычным брутом. И по конкретным доказывать вроде как нечего, формула-то одна и та же, считай хоть прямо, хоть обратно.