Date: 2011-06-18 06:57 pm (UTC)
Я уже давно не прикладной математик, но, насколько я помню, в теории сложности вычислений задачами класса P назывались задачи, для которых есть решение за полиномиальное время (т.е. функция времени от сложности задачи, например, от количества обсчитываемых вариантов, представляет из себя некий полином). Простейший пример такой задачи - сортировка массива.
Класс NP - это такой класс, где решение можно проверить за полиномиальное время, но не найдено решение, занимающее полиномиальное время. Такой задачей, например, является поиск кратчайшего пути, обходящего заданный набор точек по одному разу (задача коммивояжера) - время всех существущих решений растет экспоненциально с ростом количества точек.
Очень долго оставался открытым вопрос, равен ли класс P классу NP. Потому что, если классы равны, то для той же задачи коммивояжера существует полиномиальный алгоритм, и его нужно искать. Вопрос равенства этих классов - это вообще фундаментальный вопрос вычислительной математики, что и отражено в номере автомобиля на фотографии.
Насколько я знаю, год или два назад доказали, что эти классы не равны.
From:
Anonymous( )Anonymous This account has disabled anonymous posting.
OpenID( )OpenID You can comment on this post while signed in with an account from many other sites, once you have confirmed your email address. Sign in using OpenID.
User
Account name:
Password:
If you don't have an account you can create one now.
Subject:
HTML doesn't work in the subject.

Message:

 
Notice: This account is set to log the IP addresses of everyone who comments.
Links will be displayed as unclickable URLs to help prevent spam.

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 Aug. 20th, 2017 03:57 am
Powered by Dreamwidth Studios