Ученый из луганского вуза решил одну из математических проблем Миллениума

Профессор кафедры «Компьютерные системы и сети» Восточноукраинского национального университета имени Владимира Даля Анатолий Плотников предложил и опубликовал  в международном научном журнале «Journalofcomputerscience» (8 том, 7 выпуск) вариант решения ранее нерешенной математической задачи «PvsNP» («Класс задач Р против класса задач NP»).

Об этом сообщает пресс-служба ВНУ им. Даля.

Анатолий Плотников занимается проблемами информатики и дискретной математики с 80-х годов. Несколько лет назад далевский ученый уже предлагал мировому сообществу математиков вариант решения задачи «P vs NP», однако обнаруженный контрпример указал на частный характер решения. Поэтому Анатолий Дмитриевич продолжил работу над поиском общего решения данной задачи миллениума

Суть  проблемы  «P vs NP» заключается в поиске возможного решения задач класса NP с помощью хороших алгоритмов (то есть, за небольшой промежуток времени). Класс NP включает в себя все задачи, которые решаются на компьютере. Они имеют большую практическую значимость, однако доказательство того, что многие из них могут быть решены с помощью хорошего алгоритма, не существует. Класс задач Р, входящий в NP, напротив,можно решить с помощью хорошего алгоритма.

Анатолий Плотников отмечает, что процесс решения задач класса NP растянут по времени, а в процессе решения появляются промежуточные результаты. Профессор определяет подкласс UF задач NP, у которых промежуточные результаты можно найти за небольшое время, зависящее от размерности задачи. Так как это свойство  в определении класса NP не оговаривается, то в него могут входить задачи, для которых проверка промежуточного результата может требовать неприемлемо большого  времени. Анатолий  Дмитриевич в своем решении указывает, что UF не равен NP, а Р входит в UF. Следовательно, Р не равен NP.

Решение задачи «P vs NP» имеет важное практическое значение. В частности, оно позволяет определить пути решения многих проблем криптологии - науки, занимающейся  методами шифрования и дешифрования информации, – что поможет защитить важную информацию с ограниченным доступом (банковскую, военную, коммерческую тайну). Также полученное решение можно использовать и в других областях знания.

На данном этапе вариант решения, предложенного Анатолием Плотниковым, проходит проверку. Однако, независимо от результата, далевский ученый не собирается останавливаться на достигнутом: «Существует проблема решения задач класса UF и я планирую работать в этом направлении. Я не прекращу работать в этой области, ведь это моя жизнь».

Напомним, что задачи миллениума (Millennium Prize Problems) составляют семь математических проблем, охарактеризованных как «важные классические задачи, решение которых не найдено вот уже в течение многих лет». За решение каждой из этих проблем Институтом Клэя предложен приз в 1 000 000 долларов США. Анонсируя приз, институт Клэя провёл параллель со списком проблем Гильберта, представленным в 1900 году и оказавшим существенное влияние на математиков XX века. Из 23 проблем Гильберта большинство уже решены, и только одна — гипотеза Римана — вошла в список задач миллениума. До сих пор решена только одна из семи проблем тысячелетия (гипотеза Пуанкаре): в 2002-2003 годах ее решил российский математик Григорий Перельман.

Если вы заметили ошибку, выделите необходимый текст и нажмите Ctrl+Enter, чтобы сообщить об этом редакции
Автор
(0 оценок)
Актуальность
(0 оценок)
Изложение
(0 оценок)
472 просмотра в марте
Я рекомендую
Пока никто не рекомендует

Комментарии

Ситуация, которая сложилась в стране, не может не вызывать тревогу. Социальная напряженность растет, и это видно по тем комментариям и жарким дискуссиям, которые разгораются под каждым материалом. Мы не можем допустить, чтобы сайт использовался различными радикальными силами по обе стороны «баррикад» в качестве агитационной площадки. Поэтому вынуждены временно закрыть возможность комментирования. Предлагаем вам перенести дискуссию со страниц {url} в социальные сети, где Вы сможете выразить свою позицию. Все новости {url} доступны в группах {vkpage}, {fbpage}, {okpage}. Мир Вам и Вашим семьям.
Происшествия
Начиная с весны 2014 года в боях на Донбассе погибли 219 воинов Нацгвардии Украины. Об этом в День Национальной гвардии Украины сообщил пресс-секретарь Министерства внутренних дел Артем Шевченко. «Немного цифр на первую 5 годовщину Национальная гвардия Украины: 45000 личного состава (законом предусмотрено увеличение при необходимости к 60000) 34495 участников боевых действий; 1364 отмечены государственными наградами, в том числе 188 посмертно; три Героя Ук...
Происшествия
Силы ООС на Донбассе ликвидировали пулеметную точку боевиков ОРДЛО. Об этом на своей странице в Фейсбук сообщает офицер ВСУ Анатолий Штефан (Штирлиц). «В результате меткого выстрела уничтожена позиция российских оккупантов вместе с пулеметчиком», - написал Штефан.
Общество
Все КПВВ Донбасса на линии разграничения начали работу вовремя. Сегодня утром на КПВВ на въезд и выезд находилась такое количество транспортных средств: «Майорск» - 20/50; «Марьинка» - 20/70; «Новотроицкое» - 30/10; «Гнутово» - 20/30. Сообщает Государственная пограничная служба Украины. За прошедшие сутки, по сравнению с предыдущими, отмечалось увеличение пассажиропотока. В общем через КПВВ последовало 43,4 тысячи человек и почти 5000 транспортных средств:...
Происшествия
За сутки, 25 марта противник продолжил провокационные обстрелы позиций Объединенных сил. Как сообщает Штаб ООС зафиксировано семь нарушений режима прекращения огня, при этом дважды были применены вооружения, запрещено минскими договоренностями. Российско-оккупационные войска обстреливали позиции подразделений Объединенных сил из ствольной артиллерии калибра 122 мм, минометов калибра 82 мм, гранатометов, крупнокалиберных пулеметов и стрелкового оружия.В по...
Бизнес
К закрытию межбанка американский доллар подорожал в покупке на 9 копеек, в продаже — на 7 копеек. Евро вырос на 15 копеек в покупке и на 12 копеек в продаже, сообщает Минфин. Валюта Открытие 25 марта Закрытие 25 марта Изменения доллар 26,85/26,90 26,94/26,97 9/7 евро 30,35/30,41 30,50/30,53 15/12 рубль 0,4162/0,4172 0,4197/0,4207 0,0035/0,0035 Напомним, что торги по доллару открылись сегодня в диапазоне 26,8800/26,9100 грн/долл., торги по евро — в диапазон...
Политические новости
Шухевич уверен, что менять главнокомандующего сейчас недопустимо Народный депутат Украины Юрий Шухевич поддержал президента Украины Петра Порошенко. Об этом он заявил в специальном обращении для украинских телеканалов. Шухевич заявил, что менять главнокомандующего сейчас недопустимо. "Мы живем в очень сложное время и в данный момент менять главнокомандующего – это недопустимо. Это может привести нас к катастрофе". Сын легендарного главнокомандующего УПА Ро...
Общество
Сегодня 26 украинских строителей и 13 единиц строительной техники выехали к разрушенному российскими войсками и боевиками мосту в Станице Луганской, чтобы начать реконструкцию этого объекта. Об этом на своей странице в Фейсбук сообщила вице-спикер Верховной Рады Ирина Геращенко. "Мост оккупанты разбили в 2014, на его руинах установили российской блокпост с боевиками. Ежегодно при переходе этими руинами гибнут люди, старики ломают руки - ноги. Все эти годы...
Политика
Украина предложила Российской Федерации 30 марта провести обмен 25 украинцев, удерживаемых РФ, на 25 осужденных в Украине россиян. Об этом заявила первый вице-спикер Верховной Рады, представитель Украины в гуманитарной подгруппе Трехсторонней контактной группы Ирина Геращенко, передает "Интерфакс-Украина". "Мы с Евгением Кирилловичем Марчуком - представителем Украины в Трехсторонней контактной группе - направили 16-е письмо представителю России в Трехсторо...
Политика
Лидером среди кандидатов в президенты и в дальнейшем остается шоумен Владимир Зеленский, за которого готовы отдать свои голоса 32,1% респондентов, среди тех, кто определился с кандидатом. Об этом говорится в результатах опроса, проведенного Киевским международным институтом социологии. По данным опроса, среди тех, кто определился и намерен голосовать 17,1% украинцев планируют проголосовать за Петра Порошенко, а 12,5% - за Юлию Тимошенко. Также сообщается,...