Анатолий Васильевич Панюков около 30 лет провел в поисках решения одной из сложнейших задач тысячелетия. Математики всего мира долгие годы пытаются доказать или опровергнуть существование равенство классов P и NP, существует около сотни решений, но ни одно из них пока не было признано. По этой теме, имеющей отношение к данной проблеме,  заведующий кафедрой ЮУрГУ защитил кандидатскую и докторскую диссертации, но, как ему кажется, правильный ответ нашел только сейчас.
— Результат своей работы я обсуждал на ряде межокружных конференций и среди профессионалов. Результаты были представлены в Институте математики и механики УрО РАН и в журнале «Автоматика и механика», выпускаемом Российской Академией Наук, — рассказал «Хорошим новостям» доктор физико-математических наук Анатолий Панюков. – Чем дольше профессионалы не могут найти опровержения, тем результат считается более правильным.

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

— Большинство ученых склоняются к гипотезе, что классы P и NP не совпадают, но если в представленных доказательствах нет ошибки, то это не так, — отметил в разговоре с «Хорошими новостями» Анатолий Панюков.

Если доказательство челябинского ученого окажется верным, то это сильно повлияет на развитие математики, экономики и технических наук. Оптимизационные задачи в бизнесе будут решаться точнее, отсюда будет больше прибыли и меньше издержек у компании, которая использует специальное программное обеспечение для решения подобных задач.

Следующим шагом для признания работы челябинского ученого будет обнародование доказательства в Математическом институте Клэя, который объявил премию в миллион долларов за решение каждой из задач тысячелетия.

В настоящее время только одна из семи проблем тысячелетия (гипотеза Пуанкаре) решена. Филдсовская премия за её решение была присуждена Григорию Перельману, который отказался от неё.

http://hornews.ru/news/last_news/chelyabinskiy_matematik_reshil_odnu_iz_zadach_tyisyacheletiya.html

 

Что это вообще значит и каков практическое применение этому доказательству ?

Равенство классов P и NP доказано ( возможно)

Дело в том, что вся криптография, например, держится на том, что есть такие функции, для которых посчитать y=F(x) можно за быстрое время, а чтобы решить относительно x уравнение F(y)=x, если известно y, — нужно решать перебором, а это долго.

Можно привести пример: разложение числа на простые множители. Само разложение пока умеют делать только перебором, и это очень долго. Зато проверить результат можно просто и быстро — перемножив полученные числа.

Условно говоря, криптография делится на два типа: с открытым ключём и закрытым. С закрытым все понятно — есть некоторый ключ, который знаем только вы и я. Я шифрую им сообщение, отравляю вам, вы им расшифровываете. Если взять ключ очень большой (очень, очень большое число), то взломать нашу переписку перебором будет очень тяжело — долго перебирать.  Но есть очевидный недостаток — мы с вами не знакомы, сидим в разных городах, как нам этим ключем обменяться,  так, чтобы  его никто не перехватил?

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

Заодно ты можешь зашифровать свое сообщение закрытым ключем, я его расшифрую твоим открытым и это будет точно гарантией что это сообщение написал именно ты(больше ни у кого нет твоего закрытого ключа). Так появляется цифровая подпись(https, цифровые сертификаты, подписи драйверов, вот это все). Так вот, есть тонкий момент — зная сообщение и открый ключ, теоретически можно найти закрытый. Но на это потребуется столетия на любой современной эвм. Потому что это NP задача. Если найдут способ свести ее к P задаче, т.е решаемой за линейное время, это означает, что потенциально можно будет находить закрытый ключ не за столетья, а за дни, часы, что скомпрометирует, например, все современную электронную финансовую систему, масштаб истерики тяжело даже представить.

Однако, доказать это одно, а вот объяснить миру — другое. Недавно японец Синити Мотидзуки доказал ABC–гипотезу, так он всё доказательство честно предоставил научной общественности и удалился молча, объяснять ничего не стал, мол, вот вам материалы, — разбирайтесь. Светлые умы глянули и удивились, —  в доказательстве были использованы математические инструменты этим же Синити Мотидзуки изобретенные. То есть для того что бы разобраться нужно изучить его прошлую работу листов эдак на 500, а в прошлой работе еще куча спецсимволов, которые тоже японец для себя изобрел, ну и что бы понять их, нужно обратиться у еще одному труду Мотидзуки, а он еще на 2 тысячи страниц. В общем, в стройном математическом мире Синити Мотидзуки всё хорошо, и всё сходится, он–то для себя доказал, а вот всем остальным не очень ясно, вот так бывает — доказано вроде, но не понятно ничего.

GD Star Rating
loading...
Равенство классов P и NP доказано (возможно), 10.0 out of 10 based on 2 ratings

3 Responses to Равенство классов P и NP доказано (возможно)

  1. dick:

    Кстати, на счёт смерти криптографии я бы поостерёгся.

    Сейчас для взлома ключа n бит нужно порядка 2^n операций (или, времени).

    Если мы сменим оценку на n^100, это будет полиноминальное время, но всё–таки не линейное, и на самом деле, особо ничего не поменяется на первые годы.

  2. Жук:

    Нестрого говоря, проблема равенства P = NP состоит в следующем: если положительный ответ на какой–то вопрос можно быстро проверить (за полиномиальное время), то правда ли, что ответ на этот вопрос можно быстро найти (за полиномиальное время и используя полиномиальную память)? Другими словами, действительно ли решение задачи проверить не легче, чем его отыскать?
    Например, верно ли, что среди чисел {−2, −3, 15, 14, 7, −10, …} есть такие, что их сумма равна 0 (задача о суммах подмножеств)? Ответ да, потому что −2 −3 + 15 −10 = 0 легко проверяется несколькими сложениями (информация, необходимая для проверки положительного ответа, называется сертификатом). Следует ли отсюда, что так же легко подобрать эти числа? Проверить сертификат так же легко, как найти его? Кажется, что подобрать числа сложнее, но это не доказано.

  3. Ландау:

    Пользуясь случаем, хочу добавить, что «доказательство возможности решения задачи» совсем не тоже самое, что «решение задачи». Это для тех, кто пытается нагнетать и набрасывать на вентиляторы различно криптонаправленности.

Добавить комментарий