31 октября 2020, суббота, 20:41
VK.comFacebookTwitterTelegramInstagramYouTubeЯндекс.ДзенОдноклассники

НОВОСТИ

СТАТЬИ

PRO SCIENCE

МЕДЛЕННОЕ ЧТЕНИЕ

ЛЕКЦИИ

АВТОРЫ

18 декабря 2013, 09:59

Челябинский ученый объявил о решении одной из проблем тысячелетия

Фрагмент работы Ника Малиона (Nick Malyon) «P versus NP»
Фрагмент работы Ника Малиона (Nick Malyon) «P versus NP»
Nick Malyon
 
Интеллектуальный партнер проекта

Профессор Южно-Уральского государственного университета Анатолий Панюков сообщает, что решил ещё одну из семи проблем тысячелетия. Одну из них - гипотезу Пуанкаре - ранее доказал Григорий Перельман. На этот раз речь идёт о равенстве классов задач P и NP.

В этой проблеме идёт речь о задачах, которые решаются с помощью компьютера. Задачи из класса P - задачи, имеющие "быстрое" решение (за степенное время - которое возрастает в зависимости от количества
данных в условии, как их размер в некоторой степени - квадрат, куб, и так далее). Задачи из класса NP - задачи, для которых возможно "быстро" проверить правильность решения. Сейчас такие задачи обычно решаются перебором возможных решений с теми или иными ограничениями, уменьшающими количество подлежащих проверке вариантов. Такое решение требует экспоненциального времени, которое возрастает как e в степени, зависящей от количества данных в условии, а это намного медленнее, чем
степенное время.

Пока решение опубликовано только в журнале "Автоматика и механика". Прежде чем его признает институт Клэя, вручающий премии за решение проблем тысячелетия, оно должно подвергнуться всесторонней проверке математиков всего мира. Если доказательство окажется верным, это будет значить, что такие задачи, как "Задача коммивояжера" (поиск кратчайшего пути в объезде нескольких городов) можно будет решить "быстро", и это даст толчок новым применениям компьютеров. С другой
стороны, вся криптография с открытым ключом строится на NP-задачах (разложение числа на множители, дискретное логарифмирование), и доказательство существования "быстрого" алгоритма их решения поставит криптографию под угрозу.

Обсудите в соцсетях

«Ангара» Африка Византия Вселенная Гренландия ДНК Иерусалим КГИ Луна МГУ МФТИ Марс Монголия НАСА РБК РВК РГГУ РадиоАстрон Роскосмос Роспатент Росприроднадзор Русал СМИ Сингапур Солнце Титан Юпитер акустика антибиотики античность антропогенез археология архитектура астероиды астрофизика бактерии бедность библиотеки биоинформатика биомедицина биомеханика бионика биоразнообразие биотехнологии блогосфера вакцинация викинги вирусы воспитание вулканология гаджеты генетика география геология геофизика геохимия гравитация грибы дельфины демография демократия дети динозавры животные здоровье землетрясение змеи зоопарк зрение изобретения иммунология импорт инновации интернет инфекции ислам исламизм исследования история карикатура картография католицизм кельты кибернетика киты клад климатология клонирование комары комета кометы компаративистика космос культура культурология лазер лексика лженаука лингвистика льготы мамонты математика материаловедение медицина металлургия метеориты микробиология микроорганизмы мифология млекопитающие мозг моллюски музеи насекомые наука нацпроекты неандертальцы нейробиология неолит обезьяны общество онкология открытия палеоклиматология палеолит палеонтология память папирусы паразиты перевод питание планетология погода политика право приматы природа психиатрия психоанализ психология психофизиология птицы путешествие пчелы ракета растения религиоведение рептилии робототехника рыбы сердце смертность собаки сон социология спутники старение старообрядцы стартапы статистика такси технологии тигры топливо торнадо транспорт ураган урбанистика фармакология физика физиология фольклор химия христианство цифровизация школа экзопланеты экология электрохимия эпидемии эпидемиология этология язык Александр Беглов Алексей Ананьев Дмитрий Козак Древний Египет Западная Африка Латинская Америка НПО «Энергомаш» Нобелевская премия РКК «Энергия» Российская империя Сергиев Посад Солнечная система альтернативная энергетика аутизм биология бозон Хиггса вымирающие виды глобальное потепление грипп защита растений инвазивные виды информационные технологии искусственный интеллект история искусства история цивилизаций исчезающие языки квантовая физика квантовые технологии климатические изменения компьютерная безопасность компьютерные технологии космический мусор криминалистика культурная антропология культурные растения междисциплинарные исследования местное самоуправление мобильные приложения научный юмор облачные технологии обучение одаренные дети педагогика персональные данные подготовка космонавтов преподавание истории продолжительность жизни происхождение человека русский язык сланцевая революция физическая антропология финансовый рынок черные дыры эволюция эволюция звезд эмбриональное развитие этнические конфликты ядерная физика Вольное историческое общество Европейская южная обсерватория жизнь вне Земли естественные и точные науки НПО им.Лавочкина Центр им.Хруничева История человека. История институтов дело Baring Vostok Протон-М 3D Apple Big data Dragon Facebook Google GPS IBM MERS PayPal PRO SCIENCE видео ProScience Театр SpaceX Tesla Motors Wi-Fi

Редакция

Электронная почта: polit@polit.ru
Телефон: +7 929 588 33 89
Яндекс.Метрика Top.Mail.Ru
Свидетельство о регистрации средства массовой информации
Эл. № 77-8425 от 1 декабря 2003 года. Выдано министерством
Российской Федерации по делам печати, телерадиовещания и
средств массовой информации. Выходит с 21 февраля 1998 года.
При любом использовании материалов веб-сайта ссылка на Полит.ру обязательна.
При перепечатке в Интернете обязательна гиперссылка polit.ru.
Все права защищены и охраняются законом.
© Полит.ру, 1998–2020.