Date: 2011-06-18 12:14 am (UTC)
From: [identity profile] poslushnik.livejournal.com
Я кстати не знаю кто, но думаю не математик - я знаю кто из них у нас живет.

Date: 2011-06-18 01:30 am (UTC)
From: [identity profile] taganay.livejournal.com
Математик - это я обобщил. Скорее всего, прикладной матетаматик (который computer science). Я знаю, что вы его за математика не признаёте, но мне было лень уточнять, хотя все равно пришлось :)

Date: 2011-06-18 04:22 pm (UTC)
From: [identity profile] reytsman.livejournal.com
а просветите непричастных? а то у меня только какие то p-n-p переходы в транзисторах в голове всплывают.

Date: 2011-06-18 06:57 pm (UTC)
From: [identity profile] taganay.livejournal.com
Я уже давно не прикладной математик, но, насколько я помню, в теории сложности вычислений задачами класса P назывались задачи, для которых есть решение за полиномиальное время (т.е. функция времени от сложности задачи, например, от количества обсчитываемых вариантов, представляет из себя некий полином). Простейший пример такой задачи - сортировка массива.
Класс NP - это такой класс, где решение можно проверить за полиномиальное время, но не найдено решение, занимающее полиномиальное время. Такой задачей, например, является поиск кратчайшего пути, обходящего заданный набор точек по одному разу (задача коммивояжера) - время всех существущих решений растет экспоненциально с ростом количества точек.
Очень долго оставался открытым вопрос, равен ли класс P классу NP. Потому что, если классы равны, то для той же задачи коммивояжера существует полиномиальный алгоритм, и его нужно искать. Вопрос равенства этих классов - это вообще фундаментальный вопрос вычислительной математики, что и отражено в номере автомобиля на фотографии.
Насколько я знаю, год или два назад доказали, что эти классы не равны.

Date: 2011-06-18 11:38 pm (UTC)
From: [identity profile] poslushnik.livejournal.com
> Насколько я знаю, год или два назад доказали, что эти классы не равны

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

Date: 2011-06-19 02:41 am (UTC)
From: [identity profile] taganay.livejournal.com
Видимо, я невнимательно прочитал. Действительно, я видел только одну случайную статью - если бы доказали, это было бы повсюду.
Хотя о Перельмане, мне кажется, знают не то, что он там что-то доказал, а то, что ему давали миллион, а он не взял :)

Date: 2011-06-19 03:18 am (UTC)
From: [identity profile] poslushnik.livejournal.com
Да, личность Перельмана способствовала популярности :) Но P vs NP - тоже одна из задач на миллион.

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

Date: 2011-06-19 01:08 pm (UTC)
From: [identity profile] reytsman.livejournal.com
Ага, то есть на границе с программированием в какой то степени. Забавная вещь.

Date: 2011-06-18 11:40 pm (UTC)
From: [identity profile] poslushnik.livejournal.com
Я думаю это кто то из Computer Science Department.

Profile

poslushnik37: (Default)
poslushnik37

March 2014

S M T W T F S
       1
2345678
9101112 131415
16171819202122
23242526272829
3031     

Style Credit

Expand Cut Tags

No cut tags
Page generated Jun. 27th, 2017 10:40 pm
Powered by Dreamwidth Studios