В Луганске решена одна из задач тысячелетия

В Луганске решена одна из задач тысячелетия

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

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

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

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

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

Источник: pfoinfo.ru

Похожие новости:
Современная математика оказалась бессильна перед задачей Навье-Стокса
Лауреат Филдсовской медали математик Теренс Тао опубликовал работу, которая доказывает невозможность решения посвященной задаче Навье-Стокса проблемы тысячелетия существующими на настоящий момент средствами. Препринт (pdf) статьи доступен на arXiv.org. Тао попытался формализовать представление многих математиков ..
2014-02-26 2740 0 Научные открытия
1
Физическую «проблему тысячелетия» посчитали неразрешимой
Физики из Великобритании, Испании и Германии посчитали одну из «проблем тысячелетия» (связанную с физикой элементарных частиц) неразрешимой. Результаты своих исследований Тоби Кубитт, Дэвид Гарсия Перес и Майкл Вольф опубликовали в журнале Nature, а кратко о них сообщает Nature News.В ..
2015-12-12 2189 0 Научные открытия
-1
Челябинский ученый решил одну из семи неразрешимых задач
Математик из Челябинска Анатолий Панюков нашел решение одной из важнейших задач в современной науке. Как сообщил «Новому Региону» доктор физико-математических наук, профессор, заведующий кафедрой экономико-математических методов и статистики на факультете вычислительной математики и информатики Анатолий Панюков, с 1983 ..
2013-12-16 3034 0 Научные открытия
-1
Бабай приблизился к решению «проблемы тысячелетия»
Математик Ласло Бабай из Чикагского университета в США разработал теоретический алгоритм, позволяющий существенно ускорить сравнение графов друг с другом. Исследование ученого связано с проблемой равенства классов P и NP, являющейся одной из «проблем тысячелетия». Об этом сообщает Nature News.Исследование ученого ..
2015-11-20 3477 0 Научные открытия
0
Немецкий школьник сделал открытие в классической механике
Немецкий школьник Шаурийя Рай решил сразу две серьезные математические задачи, участвуя в конкурсе Дрезденского университета. Об этом сообщает издание The Local. Сам конкурс завершился в марте 2012 года, однако только сейчас решение школьника прошло проверку профессиональными математиками. ..
2012-05-24 2653 0 Научные открытия
0
Решена одна из старейших и сложнейших математических задач
Схематическое разбиение нескольких первых четных чисел в сумму простых. В середине мая 2013 года математик из Перу, в настоящее время работающий во Франции, Харальд Хельфготт выложил в архив препринтов Корнельского университета статью «Большие дуги для теоремы Гольдбаха». Эта статья ..
2013-06-18 3982 0 Научные открытия
0
Российский математик заявил о решении двух проблем Гильберта
Профессор Нижегородского государственного университета имени Николая Лобачевского доктор физико-математических наук Ярослав Сергеев в интервью ТАСС заявил о решении двух проблем Гильберта. Исследования опубликованы в журнале Европейского математического общества EMS Surveys in Mathematical Sciences.Первая проблема, о решении ..
2017-11-28 6167 0 Научные открытия
1
Решена полувековая задача гидродинамики
Математики и физики из Италии, США, Германии, Финляндии и Японии решили гидродинамическую задачу полувековой давности. Теоретические результаты ученые продемонстрировали в ходе экспериментов, видео которых доступно на YouTube. Исследование опубликовано в журнале Physical Review Letters, кратко о нем сообщает ..
2016-10-06 2804 0 Научные открытия
0
Ученые распутали концы света
Эксперты NASA спешат успокоить: прогнозы, будто 21 декабря 2012 г. мир сгинет в тартарары, лишены всякого основания. Развенчать апокалипсические слухи для аудитории Livescience.com взялся Дон Йоманс, возглавляющий программу NASA по наблюдению за околоземными объектами. Всем, кто переживает из-за окончания календаря ..
2011-12-13 21317 96 Научные открытия
0
В ледяной мумии учёные обнаружили самую древнюю кровь
Германо-итальянская группа учёных обнаружила в останках Этци, так называемого Тирольского ледяного человека, который жил приблизительно 5300 лет назад, красные кровяные тельца. Это самый древний биологический материал такого рода.Этци – ледяная мумия, обнаруженная в Альпах на территории Италии ..
2012-05-6 1932 0 Научные открытия
-1
Ученые научились определять массу черных дыр
Одна из основных задач астрофизики – изучение свойств галактик и  их эволюция. Однако галактика – огромная структура, и приходится учитывать свойства отдельных ее частей, особенно уникальных, таких, как черные дыры. Астрофизики разработали новый способ взвешивать черные ..
2013-01-31 1716 0 Научные открытия
0
Российские ученые пробурили 4-километровый лед в Антарктиде
После 30 лет бурения российские ученые проникли в подледниковое озеро Восток в Антарктиде, сообщил в понедельник источник в научных кругах. «Вчера на станции Восток в Антарктиде наши ученые на глубине 3,768 тыс. метров завершили бурение и достигли поверхности подледникового озера», - сказал ..
2012-02-6 5025 3 Научные открытия
-1
Ученые CERN обнаружили новые загадочные частицы
Ученые Европейской организации ядерных исследований CERN обнаружили в данных, собранных в свое время датчиками эксперимента LHCb Большого Адронного Коллайдера, следы двух новых, ранее неизвестных частиц. При этом, одна из этих частиц обладает столь уникальным ..
2014-10-13 2630 0 Научные открытия
1
Раскрыт механизм человеческой памяти
Исследователи из Массачусетской общей больницы под руководством Джошуа Роффмана (Joshua Roffman) выяснили, как дофаминовые рецепторы обеспечивают функционирование рабочей или оперативной памяти в мозге людей. В частности, было показано, что дофамин перенаправляет когнитивные ресурсы на поддержание необходимых функций мозга. ..
2016-06-05 2662 0 Научные открытия
0
Путин поставил перед российской наукой амбициозную задачу
Вручая президентские премии в области науки и инноваций за 2012 год пяти молодым ученым в Екатерининском зале Кремля, Владимир Путин отметил, что перед Россией стоят амбициозные задачи. Доцент Санкт-Петербургского госуниверситета Надежда Бокач была удостоена премии за достижения в развитии ..
2013-02-8 1674 0 Научные открытия
0