Математик - это я обобщил. Скорее всего, прикладной матетаматик (который computer science). Я знаю, что вы его за математика не признаёте, но мне было лень уточнять, хотя все равно пришлось :)
Я уже давно не прикладной математик, но, насколько я помню, в теории сложности вычислений задачами класса P назывались задачи, для которых есть решение за полиномиальное время (т.е. функция времени от сложности задачи, например, от количества обсчитываемых вариантов, представляет из себя некий полином). Простейший пример такой задачи - сортировка массива. Класс NP - это такой класс, где решение можно проверить за полиномиальное время, но не найдено решение, занимающее полиномиальное время. Такой задачей, например, является поиск кратчайшего пути, обходящего заданный набор точек по одному разу (задача коммивояжера) - время всех существущих решений растет экспоненциально с ростом количества точек. Очень долго оставался открытым вопрос, равен ли класс P классу NP. Потому что, если классы равны, то для той же задачи коммивояжера существует полиномиальный алгоритм, и его нужно искать. Вопрос равенства этих классов - это вообще фундаментальный вопрос вычислительной математики, что и отражено в номере автомобиля на фотографии. Насколько я знаю, год или два назад доказали, что эти классы не равны.
Видимо, я невнимательно прочитал. Действительно, я видел только одну случайную статью - если бы доказали, это было бы повсюду. Хотя о Перельмане, мне кажется, знают не то, что он там что-то доказал, а то, что ему давали миллион, а он не взял :)
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png)
timeasmymeasure
no subject
Date: 2011-06-18 12:03 am (UTC)no subject
Date: 2011-06-18 12:14 am (UTC)no subject
Date: 2011-06-18 01:30 am (UTC)no subject
Date: 2011-06-18 04:22 pm (UTC)no subject
Date: 2011-06-18 06:57 pm (UTC)Класс NP - это такой класс, где решение можно проверить за полиномиальное время, но не найдено решение, занимающее полиномиальное время. Такой задачей, например, является поиск кратчайшего пути, обходящего заданный набор точек по одному разу (задача коммивояжера) - время всех существущих решений растет экспоненциально с ростом количества точек.
Очень долго оставался открытым вопрос, равен ли класс P классу NP. Потому что, если классы равны, то для той же задачи коммивояжера существует полиномиальный алгоритм, и его нужно искать. Вопрос равенства этих классов - это вообще фундаментальный вопрос вычислительной математики, что и отражено в номере автомобиля на фотографии.
Насколько я знаю, год или два назад доказали, что эти классы не равны.
no subject
Date: 2011-06-18 11:38 pm (UTC)Вы что, нет конечно. Если бы доказали все бы об этом знали, как все знают о Перельмане.
no subject
Date: 2011-06-19 02:41 am (UTC)Хотя о Перельмане, мне кажется, знают не то, что он там что-то доказал, а то, что ему давали миллион, а он не взял :)
no subject
Date: 2011-06-19 03:18 am (UTC)http://www.claymath.org/millennium/P_vs_NP/
no subject
Date: 2011-06-19 01:08 pm (UTC)no subject
Date: 2011-06-18 11:40 pm (UTC)