Знай Наших !!!
Sep. 13th, 2012 10:32 pm![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
arnaut-09.livejournal.com posting in ![[community profile]](https://www.dreamwidth.org/img/silk/identity/community.png){kind=small}
urb_a
Профессор из Луганска Анатолий Плотников предложил и опубликовал в международном научном журнале Journal of computer science (8 том, 7 выпуск) вариант решения одной из так называемых "нерешаемых" математических задач P vs NP.
"Анатолий Плотников занимается проблемами информатики и дискретной математики с 80-х годов. Решение задачи P vs NP имеет важное практическое значение. В частности, оно позволяет определить пути решения многих проблем криптологии - науки, занимающейся методами шифровки и дешифровки информации, что поможет защитить информацию с ограниченным доступом (банковскую, военную, коммерческую тайну)", - сообщили в пресс-службе Восточноукраинского национального университета имени Владимира Даля.
Напомним, что так называемые задачи миллениума - это семь классических задач, решение которых не найдено. За решение каждой из них бостонский Институт Клэя предложил приз в 1 млн долларов США.
До сих пор решена только одна из семи проблем тысячелетия. Российскому математику Григорию Перельману удалось доказать гипотезу Пуанкаре в 2002-2003 годах. Однако математический гений от миллиона отказался.
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
no subject
Date: 2012-09-13 09:05 pm (UTC)no subject
Date: 2012-09-14 12:38 am (UTC)no subject
Date: 2012-09-14 01:03 am (UTC)Автор заявляет что в NP задачах есть задачи UF (не знаток направления, но чувствую что это его термин) подмножеством которых является класс P,
после чего доказывает что среди NP задач есть задачи в которых верификация занимает экспоненциальное время...
При чём верификацию он в скобочках объясняет как obtaining - хотя вроде-бы
в этой теории есть различие между верификацией ответа и нахождением ответа - верификация это подтверждение что ответ правильный,
и верификация как-раз должна быть полиномиальной если речь идёт о NP.
Если же предположить что он запутался в английском и подразумевал наличие задач требующих экспоненциального времени на решение,
то это как раз то что требуется доказать, а не что-то заранее известное. Есть задачи для которых известен только экспоненциальный метод решения, но не доказано что нет лучших решений.
В общем, не будет ему миллиона.
no subject
Date: 2012-09-14 03:10 am (UTC)no subject
Date: 2012-09-14 02:38 pm (UTC)но поскольку тема не совсем моя оставляю benefit of doubt.
no subject
Date: 2012-09-14 05:40 am (UTC)