Задача P = NP имеет решение

iri3955


Задача P = NP имеет решение Или шутка такая? Надо срочно все интренет-банкинги закрывать? Гречка опять подорожает....

elenakozl

Ну, если N=1. Или P=0. :D

Sergey79

или P=exp(* N=d/d*

JuLsJuLs

Ну раньше такие друзья и соответствующие издания сосредоточивали усилия на теореме Ферма. Но вот, видимо, за 20 лет до них дошло, что с теоремой Ферма уже поздняк. Переключились на P vs NP. Ну и пральна, не на гипотезу Римана же или гипотезу Ходжа. Так слова какие-то нипанятные...

sweettydo

Тут в моей вкшной ленте переписка небольшая завязалась. Вот цитата от одной аспирантки этого чувака:
Статья находится на рецензировании в журналах, как только она выйдет, ссылка будет опубликована на сайте нашей кафедры. Пока благодаря аспирантам Анатолия Васильевича мы вместо того, чтобы принимать зачеты и экзамены, сидим как в call-центре на телефоне и отвечаем журналистам. Собираемся выкладывать препринт на сайт нашей кафедры.
P=NP. Если в ваших диссерах используются NP-алгоритмы, торопитесь их защитить.
так что спешите защищать диссеры! :grin:

tester1

дай плиз ссылку на вконтакт это аспирантки, хочу посмотреть остальную переписку

Nefertyty

а это реально такая катастрофа для криптографии? докажут например что можно разложить число за время N^10^200 и что?

wawa321

"Доказательства" P/NP проблемы появляются довольно часто, причем примерно половина из них утверждает что P=NP, а вторая половина, то P!=NP :)

Kevin111

вроде разложение числа вообще не NP-полная задача, за корень из N делений выполняется, а деление за время пропорциональное логарифму длины числа, что меньше чем N, итого имеем что разложение делается быстрее чем (N^0.5)*log N < N^1.5

Nefertyty

вроде разложение числа вообще не NP-полная задача, за корень из N делений выполняется
тут N - это длина записи числа, то есть примерно логарифм

Kevin111

а я разве не это написал?

antonata

Нет, ты не это написал.
Показываю на примере. Пусть у тебя есть число X равное 123456789. В этом случае N = 9, а не 123 миллиона с лишним. Твои вычисления велись относительно значения числа, а не длины его записи. А значение числа как раз экспоненциально зависит от его длины. То есть в твоей формуле, если правильную вещь обозначить за N, а не то, что обозначил ты, будет
O2^N) ^0.5 * log (2^N = O(N * 2^N)
Ну и длинное деление за длину числа - это довольно круто, мне такой алгоритм не известен (хотя может быть он и существует).

Kevin111

да, напутал я.

stm7543347

P!=NP
Новые сведения!
NP на самом деле равно факториалу P! :book:

elenakozl

NP на самом деле равно факториалу P!
Очевидно, что тогда N=(P-1)!

marc

ура товарищи!
Заместителем директора казахстанского филиала МГУ, Академиком НАН РК Мухтарбаем Отелбаевым решена шестая математическая «проблема тысячелетия»
накрываем бешбармак и поздравляем второго перельмана
http://enu.kz/ru/info/novosti-enu/24698/
Мухтарбай Отелбаев, профессор, д.ф.-м.н., академик НАН РК, директор Евразийского математического института ЕНУ им. Л.Н.Гумилева, завершил и опубликовал работу «Существование сильного решения уравнения Навье-Стокса» в открытой печати.
Важность публикации заключается в том, что эта проблема включена в 7 самых сложных математических задач, которых называют «проблемами тысячелетия». Отметим, что за решение каждой из этих проблем математический Институт Клэя в начале 2000 года объявил приз в 1 млн. долларов США. В настоящее время только одна из семи проблем тысячелетия (гипотеза Пуанкаре) решена. Филдсовская премия за её решение была присуждена Григорию Перельману.
Полная статья Мухтарбая Отелбаева опубликована в «Математическом журнале» (2013, т.13, № 4 (50 http://www.math.kz/index.php/ru/513.
Напомним, в область научных интересов Мухтарбая Отелбаева входят спектральная теория операторов, теория сужения и расширения операторов, теория вложений функциональных пространств, теория приближений, вычислительная математика, обратные задачи.
Мухтарбай Отелбаев - обладатель звания «Деятель науки года» в конкурсе «Алтын адам» («Человек года в Казахстане» в номинации “Наука”) 2002 г.; 2002-2003 гг. и 2004- 2005гг. - обладатель государственной научной стипендии для ученых и специалистов, внесших выдающийся вклад в развитие науки и техники, лауреат премии Организации экономического сотрудничества в номинации "Наука и технологии", 2004 г., обладатель гранта МОН РК «Лучший преподаватель вуза», лауреат государственной премии Республики Казахстан в области науки и техники.

Arthur8

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

BSCurt

Короче, надо быстро решать, что доказывать, а то скоро всё разберут.

marc

казахстанские математики частенько сообщают о решении нерешенных задач (правда, на тысячелетия еще вроде не замахивались что сопровождается бурными аплодисментами, ломящимися от бешбармака столами и пафосными тостами
проблема в том, что и после этого задачи остаются нерешенными, а широкое научное сообщество и не в курсе, что в каком-то уголке средней азии праздновались великие математические открытия
это не все - бывает, что человек, съездив на non-degree в какой-нибудь штатовский или европейский универ, заявляет, что был там профессором и т.д.
азия - она такая... :crazy: :(

lena1978

всем известно, что проблему решил в 2010 году профессор Омуров Таалайбек Дардайылович из Кыргызского Национального университета имени Ж. Баласагына.
http://sgma.alpha-design.ru/MMORPH/N-29-html/omurov/omurov.h...

marc

Автор решения о мотивах и о том, как потратит миллион.
http://www.khabar.kz/ru/view/obwestvo/page_54251_kazakhstans...

lena1978

а может и правда доказал. интересно, сколько Фефферман будет читать.

Xephon

Из интервью:
Мухтарбай Отелбаев, профессор, академик НАН РК:
- Вы, наверное, слышали про фильм «Борат»? Примерно такое мнение о казахстанских ученых на западе. Вот это очень хотел сломить. Даже в процессе работы очень сильно похудел.

lena1978

я бегло просмотрел статью, я не спец, конечно, сильно понять не могу, но на ламерский взгляд там методы 50-70-х годов используются, это максимум, неужели просто ход нашёлся, который атцы не заметили?

lena1978

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

BSCurt

а может и правда доказал.
И опубликовал в Ведущем Научном Журнале!
но на ламерский взгляд там методы 50-70-х годов используются, это максимум,
И на мой ламерский взгляд, но видимо что умел то и пользовал.

Polyphem

Кто-нибудь изучает статью? Есть интересные мысли по поводу? :)
насколько я помню, Ольга Александровна для трёхмера доказала, что если начальное условие мало в некотором смысле, то задача имеет решение
Да, вроде бы, ты прав. Единственное, что начальное условие и внешние силы (непотенциальные) не слишком большие.
а если скорости очень большие, то уравнения теряют физический смысл, так так перестают работать допущения, использованные при их выводе
Можешь пояснить эту мысль, пожалуйста. Ведь для вязкой жидкости силы трения пропорциональны не деформациям, а скоростям деформаций, поэтому важны не сами скорости, а их градиенты. И ещё, скорости и градиенты не могут же быть "слишком большими", поскольку для них в L_2 всегда есть оценка сверху через начальные условия и внешние силы.

marc

Кто-нибудь изучает статью? Есть интересные мысли по поводу?
мысль такая: если сравнивать со статьями Гриши Перельмана ( http://arxiv.org/pdf/math/0303109v1.pdf ) и Эндрю Уайлса ( http://www.cs.berkeley.edu/~anindya/fermat.pdf то сабж на ламерский взгляд выглядит как из рогатки по самолету

BSCurt

если сравнивать со статьями Гриши Перельмана ( http://arxiv.org/pdf/math/0303109v1.pdf ) и Эндрю Уайлса ( http://www.cs.berkeley.edu/~anindya/fermat.pdf то сабж на ламерский взгляд выглядит как из рогатки по самолету
Ну тут есть одно концептуальное замечание, что гипотеза Пуанкаре, что теорема Ферма, хоть и формулируются весьма просто, но идейно относятся к более "высокой науке" чем Навье-Стокс.

Polyphem

Ну тут есть одно концептуальное замечание...
... но идейно относятся к более "высокой науке" чем Навье-Стокс
Не-не-не. Не надо концептуальных замечаний, приводящих к холивару :)

marc

Ну тут есть одно концептуальное замечание, что гипотеза Пуанкаре, что теорема Ферма, хоть и формулируются весьма просто, но идейно относятся к более "высокой науке" чем Навье-Стокс.
поясни плз, начальные такие:
Навье-Стокс не решен, имеет много приложений и следствий из решения.
Ферма решен, абсолютно бессмысленен по формулировке, но в процессе решения аж выделился новый раздел.
Пуанкаре решен, что с этим делают дальше - не знаю.

Valeryk

А это типа у математиков такая фишка-называться уменьшительно-ласкательными именами?
Гриша Перельман, Миша Вербицкий и т.д.?

BSCurt

Гриша Перельман, Миша Вербицкий и т.д.?
Это видимо чтобы не быть для цивилизованных людей трудно выговариваемыми
Grigori и Mikhail

marc

Гриша Перельман, Миша Вербицкий и т.д.?
Терри Тао, Миша Громов

Niklz

это, наверное, такой анти-пафос, должно оттенять значимость результатов.

BSCurt

поясни плз, начальные такие:
Что пояснить?
Навье-Стокс не решен, имеет много приложений и следствий из решения.
Кстати какие, в смысле допустим докажут, что хорошо решение существует и что тогда?

Niklz

а кто в курсе по каким критериям включали задачи в этот список?

marc

Что пояснить?
Пояснить "гипотеза Пуанкаре, что теорема Ферма, хоть и формулируются весьма просто, но идейно относятся к более "высокой науке" чем Навье-Стокс."

BSCurt

Вики пишет «важные классические задачи, решение которых не найдено вот уже в течение многих лет»
тут вроде про процедуру отбора пишут http://www.ams.org/notices/200606/fea-jaffe.pdf

Niklz

а, так это просто пиар-ход новосозданного института. неудивительно, что Гриша от такого приза отказался.

BSCurt

Ну как бы дифуры менее "высокая наука", мне кажется, чем алгебраическая геометрия, алгебраическая топология, теория чисел и дифгем к которым относятся те две проблемы, типо по этому вероятно ожидать, что доказательство теоремы Ферма может выглядеть, как очень сильное колдунство, а Навье-Стокса как дедовские методы. Хотя с другой стороны, читал тут "Топологические методы в гидродинамике" Арнольда там тоже хватает всяких возвышенных материй, но не факт что это не забивание гвоздей микроскопом.

BSCurt

а, так это просто пиар-ход новосозданного института. неудивительно, что Гриша от такого приза отказался.
Ну как бы за доказательство обобщенной гипотезы Пуанкаре уже дважды давали Филдса.
От Филдса Гриша тоже отказался.

lena1978

ну да, про скорости я затупил.
это были воспоминания, связанные с этим интересным абзацем у Ладыженской:

lena1978

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

BSCurt

Возможно так и есть.

griz_a

Ты так реагируешь, как будто "высокая наука" - это что-то хорошее :)

marc

Ты так реагируешь, как будто "высокая наука" - это что-то хорошее
На самом деле я свой вопрос задавала нейтрально.
По ответу сложилось впечатление, что у этакий снобизм алгебраического геометра, ну примерно как у Миши Вербицкого :)

stream999


Полная статья Мухтарбая Отелбаева опубликована в «Математическом журнале» (2013, т.13, № 4 (50 http://www.math.kz/index.php/ru/513.
дайте нормальную ссылку - эта у меня не загружается, говорит циклическая переадресация

stream999


мысль такая: если сравнивать со статьями Гриши Перельмана ( http://arxiv.org/pdf/math/0303109v1.pdf ) и Эндрю Уайлса ( http://www.cs.berkeley.edu/~anindya/fermat.pdf то сабж на ламерский взгляд выглядит как из рогатки по самолету
удивляюсь я вам, как можно сравнивать статьи на разную тему. Лучше дайте концептуальный пересказ приведенного доказательства.

marc

собсно, начинают проясняться мотивы:
http://news.nur.kz/298138.html
В соавторстве с ученым Табылды Каюповым мы придумали двигатель внутреннего сгорания, работающий на совершенно новом эргономическом принципе. А еще я придумал способ полета в атмосфере :shocked: :grin: , основанный на очень экономном потреблении энергии. К сожалению, до сих пор реализовать эти проекты у меня не получалось. Псевдоученые не давали. Может быть теперь, при поддержке нашего президента, я смогу воплотить их в жизнь

marc

Апдейт
К основной теореме Отелбаева построен контрпример: http://dy.ru/post817605.html#p817605,
с которым Отелбаев согласился и добавил дополнительное условие: http://dy.ru/post818309.html#p818309,
но и это не помешало Тао модифицировать контрпример так, что он подходит и под это условие: http://math.stackexchange.com/questions/634890/has-prof-otel...

Sergey79

К основной теореме Отелбаева построен контрпример
Работаю в Алматы уже 2-й год и здесь у нас есть сильная группа (российских) математиков. В прошлов году Отелбаев вышел в свет со своим результатом, выступил на локальных конференциях и раздал нам текст. Мы почти сразу нашли там дырку. Как вы правильно заметили, все тараканы в продолжении решения по параметру. Никаких новых идей (априорных оценок) нет, а результат вроде есть.
Мухтарбай пропал почти на год, вышел с новым (по сути тем же) доказательством, но нам его не показал и опубликовали без нашего согласия (мой товарищ входящий в редакцию был против). За то что мы нашли в прошлом док-ве дырку спасибо сказано не было. К тому же ин-т математики включил нас (уже после публикации!) в комиссию по проверке правильности результата. Я думаю мы бы разобрались. Ничего сложного нет. Только время жалко

Xephon

Работаю в Алматы уже 2-й год и здесь у нас есть сильная группа (российских) математиков. В прошлов году Отелбаев вышел в свет со своим результатом, выступил на локальных конференциях и раздал нам текст. Мы почти сразу нашли там дырку. Как вы правильно заметили, все тараканы в продолжении решения по параметру. Никаких новых идей (априорных оценок) нет, а результат вроде есть.
Мухтарбай пропал почти на год, вышел с новым (по сути тем же) доказательством, но нам его не показал и опубликовали без нашего согласия (мой товарищ входящий в редакцию был против). За то что мы нашли в прошлом док-ве дырку спасибо сказано не было. К тому же ин-т математики включил нас (уже после публикации!) в комиссию по проверке правильности результата. Я думаю мы бы разобрались. Ничего сложного нет. Только время жалко

А кто автор этого текста?
Кстати, известно, кто автор контрпримера на dy?
Первый раз вижу ссылку на русскоязычный форум в буржуйском обсуждении. Даже гордо стало! :)

marc

 
А кто автор этого текста?
Кстати, известно, кто автор контрпримера на dy?

Автор текста — Мейрманов Анварбек Мукатович, работал в Новосибирске и Белгороде.
Автор контрпримера sup — внезапно ( http://dy.ru/post819594.html#p819594 ) ученик Мейрманова с НГУ.
 
Первый раз вижу ссылку на русскоязычный форум в буржуйском обсуждении. Даже гордо стало! :)

Справедливости ради, в обсуждении русскоязычной статьи.

Sergey79

С интересом слежу за развитием событий на dy, благо математика в отелбаевском док-ве Навье-Стокса достаточно проста.
===========
Дальше прогноз: Отелбаев скоро выступит с доп. условием, к которому опять найдут контрпример (ошибку). Но Отелбаев не остановится и возьмет свое измором. Когда всем надоест и ему никто не ответит, он раструбит, что все доказано и все согласились. Многочисленная армия поклонников добавит в книгу главу о "драматичном решении проблемы".
Тут многие экстраполируют ситуацию на весь Казахстан и всех казахов, а мне обидно. Что называется если бы. Яркий пример с этого форума.
Юзер almatynets это Садыбеков Махмуд Абдысаметович, доктор наук (ученик Кальменова автор 4 и 8 разделов статьи Отелбаева. И этот человек не чурается публично открыто обозвать м***ком и нагло обвинить во лжи уважаемого человека, Мейрманова Анварбека Мукатовича. А теперь представьте как происходит личное общение математиков в Казахстане.
Махмуд младше Анварбека Мукатовича лет на 15, по вбиваемым с детства казахским правилам должен выказывать внешнее уважение.
Понимаете, эти люди ни русские, ни казахи, и им ни капли не стыдно безнаказанностью, вседозволенностью переступать все границы не только научной среды, но даже среднего обычного человеческого общения. Это казаха можно обозвать м***даком или проигнорировать в лучшем случае, с Тао надо считаться и Тао надо отвечать по-научному (а к этому-то не привыкли). Поэтому на ваш взгляд все происходящее такая дикость (ответы на форуме через третьих лиц, молчание, отсутствие официальных новостей об ошибке а в Казахстане норма. Так получилось. Впрочем, каждый имеет то что заслуживает.

Sergey79

я бегло просмотрел статью, я не спец, конечно, сильно понять не могу, но на ламерский взгляд там методы 50-70-х годов используются, это максимум, неужели просто ход нашёлся, который атцы не заметили?
ну вот спецов задолбало и они сейчас написали статью, в которой доказали, что подобные методы (как у Отелбаева) в принципе не могут доказать существование хорошего решения.
Интересно что теперь будет с работой Отелбаева

Polyphem

ну вот спецов задолбало и они сейчас написали статью, в которой доказали, что подобные методы (как у Отелбаева) в принципе не могут доказать существование хорошего решения
О какой статье идёт речь?

shale60

ну вот спецов задолбало и они сейчас написали статью, в которой доказали, что подобные методы (как у Отелбаева) в принципе не могут доказать существование хорошего решения.
а как вообще впринципе доказываются теоремы о том, что какой-то метод не может привести к решению ныне нерешенной задачи? (я понимаю, что если бы было доказательство, что решение обязано лежать в каком-нибудь классе, но тут же не решение, а доказательство не может лежать в "классе")
Никогда не сталкивался ни с чем подобным, можно какой-нибудь подъемный пример из других областей математики? :)

vsjshnikova

Никогда не сталкивался ни с чем подобным, можно какой-нибудь подъемный пример из других областей математики?
По P!=NP есть несколько таких результатов. Самый простой - барьер релятивизации: вместо обычных алгоритмов можно рассматривать алгоритмы с доступом к некотору черному ящику. Известно, что есть черные ящики, для которых будет справедливо P!=NP, и есть те, для которых P=NP. Это значит, что доказательство для обычного случая не должно обобщаться на случай машин с черным ящиком.

Thanhsoa

Через формализацию подхода, вероятно.
Подъемный пример - задачи о невозможности построения чего-либо циркулем и линейкой (квадратура круга, трисекция угла, удвоение куба). В них формализуется понятие построения циркулем и линейкой. Идея состоит в том, что если у нас есть некий начальный отрезок на плоскости, который мы принимаем за единицу, то можно выбрать евклидову систему координат, в которой этот отрезок будет задавать вектор (1, 0). Далее, если мы будем вести построения, то новые точки могут быть получены только многократным пересечением прямых и окружностей. Соответственно каждая новая точка является решением одной из систем уравнений:
{уравнение прямой 1, уравнение прямой 2}
{уравнение окружности 1, уравнение окружности 2}
{уравнение окружности 1, уравнение прямой 2}
Решение каждого из этих уравнений выражается композицией арифметических операций и радикалов из коэффициентов. Отсюда следует, что координаты всех точек, которые мы получим в процессе наших построений, будут также выражаться через композицию арифметических операций и радикалов от рациональных чисел.
Ну а дальше уже чисто математическая задача - доказать, что кубический корень из 2 и Пи не выражаются через такую композицию.

Sergey79

но тут же не решение, а доказательство не может лежать в "классе"
Как делали многие (и Отелбаев в частности): переформулировали задачу о НС на языке абстрактных (более удобных) операторов, удовлетворяющих какому-то перечню свойств. Так вот, теперь построен контр-пример: реальное уравнение ("квази"-НС операторы из которого удовлетворяют как раз этому перечню свойств. Но это уравнение подобрано так, что для него можно построить "плохое" решение явным образом.
Отсюда делается вывод, что
1) нельзя так просто заменять операторы из НС на некие абстрактные (как в частности делал Отелбаев) - надо работать с тем что есть
2) скорее всего и у НС есть плохое решение, ибо не видно откуда операторы НС могут взять дополнительные классные свойства, чтобы избегать плохих решений. Для этого нужно подробно протестировать конкретно операторы из НС на наличие этих определенных свойств.

Polyphem

ибо не видно откуда операторы НС могут взять дополнительные классные свойства
Для нелинейности в Навье-Стоксе выполнено больше, чем (B(u, u u) = 0, а именно, (B(u,u u^a) = 0 для любого a > 0. Кроме того, для двумерного случая всё доказано (существование решения на всем временном промежутке). Но, однако, не исключено, что для 3-x мерного случая действительно такого нет.

marc

Поэтому на ваш взгляд все происходящее такая дикость (ответы на форуме через третьих лиц, молчание, отсутствие официальных новостей об ошибке а в Казахстане норма.
Собственно, казахи в своем репертуаре.
http://www.zakon.kz/4601272-amerikanskijj-uchenyjj-oproverg....
Американский ученый Теренс Тао поставил под сомнение решение уравнения Новье-Стокса, которое предложил казахстанский академик Мухтарбай Отелбаев, сообщает Zakon.kz.
После того, как Мухтарбай Отелбаев предоставил свое решение уравнения в научном мире началось бурное обсуждение его работы. Решением академика также заинтересовался 38-летний ученый и даже предоставил контрпример, опровергающий некоторые утверждения работы Отелбаева.
Как сообщил кандидат физико-математических наук, профессор Махмуд Садыбеков, контрпример пока не подтвержден и не опровергнут. Обсуждение работы проходит в открытом доступе и сейчас все участники научного мира могут предоставить свои доказательства или опровержения уравнения.
По его словам, на обсуждение решения уравнения может уйти примерно полгода, после чего будет создана специальная комиссия для изучения решения.
Как он заявил, в мировом ученом сообществе работу Отелбаева оценили достаточно высоко, а если в ней и есть некоторые погрешности, то они невелики.
Напомним, в начале года Мухтарбек Отелбаев заявил, что решил уравнение Новье-Стокса, входящее в список семи нерешенных «проблем тысячелетия». Ранее одну из таких «проблем», гипотезу Пуанкаре, доказал российский математик Григорий Перельман в 2006 году. Сейчас «проблем тысячелетия» всего шесть. За решение каждой из них Математический институт Клэя в Кембридже пообещал один миллион долларов.

avgustinka

так чего там с P=NP-то? а то скатился тред в сплошной Навье-Стокс. :-)

stm7543347

P=NP тогда и только тогда, когда уравнение Навье-Стокса аналитически разрешимо в радикалах. :umnik:
Оставить комментарий
Имя или ник:
Комментарий: