a car parked in my appartment complex

[poslushnik37]

Comments

[taganay.livejournal.com]

Математик из России, догадался гениальный разведчик.

[poslushnik.livejournal.com]

Я кстати не знаю кто, но думаю не математик - я знаю кто из них у нас живет.

[taganay.livejournal.com]

Математик - это я обобщил. Скорее всего, прикладной матетаматик (который computer science). Я знаю, что вы его за математика не признаёте, но мне было лень уточнять, хотя все равно пришлось :)

[reytsman.livejournal.com]

а просветите непричастных? а то у меня только какие то p-n-p переходы в транзисторах в голове всплывают.

[taganay.livejournal.com]

Я уже давно не прикладной математик, но, насколько я помню, в теории сложности вычислений задачами класса P назывались задачи, для которых есть решение за полиномиальное время (т.е. функция времени от сложности задачи, например, от количества обсчитываемых вариантов, представляет из себя некий полином). Простейший пример такой задачи - сортировка массива.
Класс NP - это такой класс, где решение можно проверить за полиномиальное время, но не найдено решение, занимающее полиномиальное время. Такой задачей, например, является поиск кратчайшего пути, обходящего заданный набор точек по одному разу (задача коммивояжера) - время всех существущих решений растет экспоненциально с ростом количества точек.
Очень долго оставался открытым вопрос, равен ли класс P классу NP. Потому что, если классы равны, то для той же задачи коммивояжера существует полиномиальный алгоритм, и его нужно искать. Вопрос равенства этих классов - это вообще фундаментальный вопрос вычислительной математики, что и отражено в номере автомобиля на фотографии.
Насколько я знаю, год или два назад доказали, что эти классы не равны.

[poslushnik.livejournal.com]

> Насколько я знаю, год или два назад доказали, что эти классы не равны

Вы что, нет конечно. Если бы доказали все бы об этом знали, как все знают о Перельмане.

[poslushnik.livejournal.com]

Я думаю это кто то из Computer Science Department.

[taganay.livejournal.com]

Видимо, я невнимательно прочитал. Действительно, я видел только одну случайную статью - если бы доказали, это было бы повсюду.
Хотя о Перельмане, мне кажется, знают не то, что он там что-то доказал, а то, что ему давали миллион, а он не взял :)

[poslushnik.livejournal.com]

Да, личность Перельмана способствовала популярности :) Но P vs NP - тоже одна из задач на миллион.

http://www.claymath.org/millennium/P_vs_NP/

[reytsman.livejournal.com]

Ага, то есть на границе с программированием в какой то степени. Забавная вещь.