Annual Open Tech Conference - ISsoft Insights 2021. June 19. Learn more.
×Закрыть

P vs NP — неужто проблема решена?!

вон оно че: www.hpl.hp.com/...apers/pnp_preliminary.pdf


некто из Аш-Пи Лабс полагает, что решил Проблему Тысячелетия.


какие у кого интуитивные предположения на этот счет? прав мужык, аль нет?


обсуждаем.

👍НравитсяПонравилось0
В избранноеВ избранном0
LinkedIn
Допустимые теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Допустимые теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter

Хм, а вот история учит, что они не только шахматы придумали... en.wikipedia.org/...ian_mathematics

математика (как точная наука) и индусы — вещи несовместимые.

ставлю 10 баксов что индус обломается.

Я видел этот сайт и даже зарегестрировался там, но статьи про колонко ориентированные базы данных там сверху не лежат к сожалению.

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

Но есть и статья. Есть на Ей-Си-Ем, но платно конечно. Но есть и бесплатная: A Common Database Approach for OLTP and OLAP Using an In-Memory Column Database

что то я суть потерял — скажем что, сложно было в НИИ устроиться, считаться научным сотрудником, и работать якобы над какими то теоретическими или практическими проблемами? Врядли. Просто ЗП низкая, перспектив мало и это отпугивает...

а многие профессии слишком сложны, чтоб там было много людей. не зависимо от спроса. скажем физик-теоретик и т.п.

Один только факультет знаю в Украине, откуда могут еще выйти серьезные математики — это физмат КПИ. Не знаю как там сейчас, но раньше туда шли талантливые ребята — призеры международных олимпиад по математике и физике, учиться там было тяжело и выпускники шли работать в R& D.

Та же прикладная математика КПИ — раньше (при СССР) выпускники шли работать в НИИ сражаться с ЕС ЭВМ, получали повышенную ЗП сразу же как младшие научные сотрудники. Сейчас — из моей группы только одного знаю что пошел работать и как то математику применяет, остальные кто куда.

подскажу, хотя особо шастать и не надо: -) при запросе «sapphire 2010» у меня в Гугле пятая ссылка прям на оф.сайт: www.sapphirenow.com

Я видел этот сайт и даже зарегестрировался там, но статьи про колонко ориентированные базы данных там сверху не лежат к сожалению.

— я именно поэтому и упомянул о нем, как контраргумент на фразу про сумасшедших ученых на гос. подаяниях. Но Кодд был ученым, он работал в Исследовательском Центре Ай-Би-Ем, а не просто в Ай-Би-Ем. Я прав?

Я не знаю, насколько я понимаю он работал в лаборатотии IBM над дисковой системой, то есть был типичным программистом в современном понимании, другое дело что тогда программирование еще было очень инновационным и таких людей наверное называли иследователями и работали они в белых халатах.

Кстати, я вот пошастал по сайтам и не нашел где можно посмотреть статьи/презентации, может подскажете?

подскажу, хотя особо шастать и не надо: -) при запросе «sapphire 2010» у меня в Гугле пятая ссылка прям на оф.сайт: www.sapphirenow.com

По факту он не был гос ученым

— я именно поэтому и упомянул о нем, как контраргумент на фразу про сумасшедших ученых на гос. подаяниях. Но Кодд был ученым, он работал в Исследовательском Центре Ай-Би-Ем, а не просто в Ай-Би-Ем. Я прав?
А насчет рел. модели: ну очень-очень спорный вопрос. Если смотреть википедию, то МайкроДБМС разрабатывалась с 1968 года. Об этом я узнал благодаря вам, признаю. О более надежных источниках и тем более других примерах не знаю и подавно. Кем и где особо использовались реляционные модели до 1969 года? Заметьте, я не отрицаю вашей правоты. Я лишь не имею ни подтверждений, ни опровержений.
А упомянул Кодда я как основоположника РДБМС, кем он и является. И согласитесь, упомянул заслуженно. В том виде, в котором модель была имплементирована, ее сформулировал именно Кодд.

Вобщем-то, не сильно я исказил факты, согласитесь: -)

Об этом было на SAPPHIRE-2010, если вам это интересно, конечно.

Кстати, я вот пошастал по сайтам и не нашел где можно посмотреть статьи/презентации, может подскажете?

например какие?

О том что Код был гос. ученым, и он придумал реляционную модель в своей статье. По факту он не был гос ученым, и реляционные модели использовались до его статьи.

Да это не претензии, только если бы повсеместно они использовались (=> с них большой прок), то эти продукты были бы у всех на слуху, все бы их знали, а не только википедия, в этом я и вижу разницу. Только это и хотел сказать. Возможно я ошибаюсь и просто ни я, ни кто-то со знакомых с областями, где от этих баз большая выгода, просто не сталкивались.

Они повсеместно используются, почти любой OLAP oriented storage имеет в себе column oriented идеи. С гугловым BigTable тоже можно работать как с column oriented DB.

Я своим коментарием лишь хотел показать что вы сильно исказили факты.

например какие?


crypto5

жесть — это ваши пустые комментарии. что вы пытались показать — неясно. я своим комментарием лишь показал, что любые упомянутые «тренды» исходят как раз от научных исследований. и это действительно так. и Кодд был именно ученым. Откройте хотя бы Википедию и посмотрите когда, где и чем он занимался.

Я своим коментарием лишь хотел показать что вы сильно исказили факты.

Да это не претензии, только если бы повсеместно они использовались (=> с них большой прок), то эти продукты были бы у всех на слуху, все бы их знали, а не только википедия, в этом я и вижу разницу. Только это и хотел сказать. Возможно я ошибаюсь и просто ни я, ни кто-то со знакомых с областями, где от этих баз большая выгода, просто не сталкивались.

crypto5

жесть — это ваши пустые комментарии. что вы пытались показать — неясно. я своим комментарием лишь показал, что любые упомянутые «тренды» исходят как раз от научных исследований. и это действительно так. и Кодд был именно ученым. Откройте хотя бы Википедию и посмотрите когда, где и чем он занимался.

Прикольно, то есть колоночные БД уже много лет шагают по земле (у того же Оракла в том числе), а академия только проснулась?

— рассказывать все в деталях не собираюсь, но естесственно «академия» (?) не только проснулась. Об этом было на SAPPHIRE-2010, если вам это интересно, конечно.


это количество дворников\грузчиков\жавакодеров диктуется спросом.,

а многие профессии слишком сложны, чтоб там было много людей. не зависимо от спроса. скажем физик-теоретик и т.п.

Ой да ладно. Все мы когда то учили высшую математику в школах или ВУЗах. И она тогда не казалась чем-то непостижимо далеким. На ура счелкали интегралы и логарифмы любой сложности. Вот токо беда, небыло практики и со временем все забылось. Я вас уверяю, усли бы спрос на вышку был такой же как на говнокодинг, то математиков бы сейчас было больше чем бухгалтеров.

Кстати, не зря даже Нобелевскую премию не дают за достижения в области математики...

вы просили примеры комерческих продуктов, в википедии их есть. В дополнение я работаю с HBase, вот примеры ее использования: wiki.apache.org/...base/PoweredBy

И я не совсем понял в чем разница между примерами из википедии, и примерами из моего опыта, это как то меняет обьективную реальность?

Спасибо за очередное напоминание о существовании википедии, только из предыдущего вашего сообщения у меня сложилось мнение, что вы сможете без интернета назвать продукты, использующие эти «Column-oriented DBMS», а гуглить умею и я. Смотрю. Знакомое слово Sybase, но здесь Sybase IQ. Остальные типа Valentina Database даже понятно, что не зацепятся в памяти.

Спасибо, КО.


А по каким материкам шагают эти колоночные БД, что я о них первый раз слышу?
Можно линки примеров коммерческого использования?

en.wikipedia.org/...n-oriented_DBMS с уважением, ваш КО, так вроде говорят?; -)

2 Сергей Волошин

Должна быть гласность в математике и не должно быть демократии

А по каким материкам шагают эти колоночные БД, что я о них первый раз слышу?

Можно линки примеров коммерческого использования?

А бывают б... плохие математики или теоретические физики? Ну такие, которые всю жизнь работали, получали какие-то гранты, а так ничего и не открыли и не изобрели. Вы их уважаете так же как и «джава-кодерков» или больше?

Вы не поверите, но колоночные базы данных исследуются в институте Хассо Платтнера, недавними аспирантами, абы потом эти наработки воплотить в жизнь в трендовом SAPe.

Прикольно, то есть колоночные БД уже много лет шагают по земле (у того же Оракла в том числе), а академия только проснулась?

мы все верим вашему опыту. но, вы не поверите: когда-то давно некто Эдгар Франк Кодд (сумасшедший ученый, живущий на гос.подаяние?!) создал реляционную модель данных

Жесть, ниче что Код работал в IBM, и до его статьи у IBM уже была MicroDBMS, реализующая реляционную модель? И конечно же никаких P и NP там не было...

> то уже завтра мы бы имели на выходе 100500 математиков на любой вкус и цвет.
это количество дворников\грузчиков\жавакодеров диктуется спросом.,

а многие профессии слишком сложны, чтоб там было много людей. не зависимо от спроса. скажем физик-теоретик и т.п.

А джава-кодерков туда не допустят.

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

И смею вас заверить, что если бы знания математики были так же востребованы как жава/дотнето кодеризм, то уже завтра мы бы имели на выходе 100500 математиков на любой вкус и цвет.


проджектменеджер 10 час. назад

Если ваше представление об IT сводится исключительно к системам управления складом и логистикой, могу лишь сожалеть. В мире делается очень много интересных проэктов в том числе и в области ИИ, и в том числе ИИ для управления автомобилем ec.europa.eu/...08_04_01_en.htm

Во всяком случае там не индусы и люди у которых математическое образование НАМНОГО выше среднего. А джава-кодерков туда не допустят.

кому интересно, Стивен Кук (автор проблемы) на 2х страничках излагает некоторые последствия решения проблемы: http://www.ms.unimelb.edu.au/~woodd/NetOpt/Cook-PNP-JACM.pdf

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

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

но поверьте уж моему опыту

мы все верим вашему опыту. но, вы не поверите: когда-то давно некто Эдгар Франк Кодд (сумасшедший ученый, живущий на гос.подаяние?!) создал реляционную модель данных. И именно его статья вдохновила Ларри Эллисона на создание горячо любимого вами Оракла. Вы, простите, приблизительно представляете о чем речь? А сколько «трендовых» словечек в той статье? Вы не поверите, но колоночные базы данных исследуются в институте Хассо Платтнера, недавними аспирантами, абы потом эти наработки воплотить в жизнь в трендовом SAPe. Абы вы потом рассказали нам всем, сколько прозы в проектах по разработке Оракл. Да-да.

Если ваше представление об IT сводится исключительно к системам управления складом и логистикой, могу лишь сожалеть. В мире делается очень много интересных проэктов в том числе и в области ИИ, и в том числе ИИ для управления автомобилем ec.europa.eu/...08_04_01_en.htm

Корпоративные системы тоже часто отличаются повышенной сложностью, высокими нагрузками, и большой степенью ответственности, так как там обрабатываются миллиарды долларов. А еще пишутся операционные системы, делаются инфраструктуры cloud computing, пишутся специализированные и общего назначения базы данных, создаются новые роботизированные устройства. Мне кажется вы сильно преувеличиваете.


проджектменеджер 1 час назад
ну не всем же формы шлепать да и хмл-ки править.
Да что вы говорите? Кому вообще нужны эти P и NP? Только кучке сумасшедших ученых, которые живут на гос. подаяния. Смотрите на тренды идустрии, учите Oracle,.NET, Java EE, SAP, и вам не прийдется сублимировать ваши жизненные неурядицы в псевдонаучных дискусиях!
И написать ышшо один Склад-2010. Проблема IT в том, что она уже неспособна создать ничего нового, все псевдоновое ремейк старых технологий. Поэтому и для большинства задач достаточно или готового Опенсоурса или Excel. А новых задач для решения на старых технологиях становится всё меньше и меньше.
Во к примеру, насколько сложно написать автоводителя транспорта, чтобы он полностью заменил человека? Ведь мощности компьютера это уже позволяют, просто специалистов нет. И часть библиотек даже есть (построение трехмерного изображения по двум двухмерным).

А на новые «Склады» деньги выделят разве что для получения откатов.

Во первых я вам не деточка, во вторых, можно подумать что от осознания что P = NP или наоборот индийский разработчики оракла сделают его в два раза быстрее. Внутренности оракла не строятся на таких оторванных от жизни подходах. Возможно вам не видны направления развития индустрии, вы судя по нику недавний аспирант, но поверьте уж моему опыту, в проэктах уровня разработки RDBMS Oracle обычно все намного прозаичнее, и решающую роль играют на много более hands-on подходы.

деточка, кто-то твои ораклы пишет.

ну не всем же формы шлепать да и хмл-ки править.

Да что вы говорите? Кому вообще нужны эти P и NP? Только кучке сумасшедших ученых, которые живут на гос. подаяния. Смотрите на тренды идустрии, учите Oracle,.NET, Java EE, SAP, и вам не прийдется сублимировать ваши жизненные неурядицы в псевдонаучных дискусиях!

плюс мильён

можно подумать кто то силой заставляет Сашка читать этот топик; -)


upload.wikimedia.org/...ity_classes.svg
и
upload.wikimedia.org/...ete_np-hard.svg
картинка слева.

отвечает на твой вопрос?

Очевидно же что не отвечает!

> плюс мильён

ну не всем же формы шлепать да и хмл-ки править.

А то всякой ерундой мозги парите

плюс мильён

Обсуждаемая гипотеза ведь не утверждает что любая НП задача не является П?

Да вроде не любая, а только NP-hard.

Дык одно другому не мешает!

Да че вы тут обсуждаете.
Сходили бы в Арену потусили что ли
Или съездили куда то в отпуск

А то всякой ерундой мозги парите

лично ты можешь делать все, что хочешь, но я думаю, что не стоит.

Почему? Обсуждаемая гипотеза ведь не утверждает что любая НП задача не является П? Так что вполне рационально продолжать искать П решения для НП задач.

> А в противном случае нельзя?; -)

лично ты можешь делать все, что хочешь, но я думаю, что не стоит.

что если П = НП, то можно пытаться искать П решения для НП-полных\сложных задач

А в противном случае нельзя?; -)

а ну и да. уже нашли более чем 9000 ошибок в доказательстве. так что все ок.

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

Major (unfixable) flaw found in P! =NP paper: bit.ly/cPQIlj

Ну, а что, такой результат угадывался даже интуитивно:)

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

Кстати, линейное и полиномиальное время это сильно большие разницы;) особенно для N 10^6 и больше;)

Вторый ангел вострубил


Я указал смысл теоремы на пальцах, что оно такое и нафига оно нужно.

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

Ну так вы перевели сильно исказив суть.

Я так делать не хочу, тем более я тоже считаю что данная проблема никак не поменяет образ жизни 99.999% как быдло так и не быдло программистов.


crypto5 34 мин. назад
Просто адский вывод; -)

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

Я указал смысл теоремы на пальцах, что оно такое и нафига оно нужно.

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

сё очень просто. Доказано что решение задач коммивояжера, или расписания, или распознавания голоса (тоесть те в которых N элементов системы могут находится в P состояниях N^P) невозможно математически свести к линейному математическому алгоритму P.

Просто адский вывод; -)

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

Т.е. программирование с использованием паттернов — это уже быдлокодинг, а реальные пацаны щелкают эвристиками NP-полные задачи. Кузяво.


Аноним 33 сек. назад

Я прикладной быдлокодер и не могу понять всей глубины математических выкладок в сабже. Да я даже не могу понять о чем там вообще речь.

Всё очень просто. Доказано что решение задач коммивояжера, или расписания, или распознавания голоса (тоесть те в которых N элементов системы могут находится в P состояниях N^P) невозможно математически свести к линейному математическому алгоритму P. И решение таких задач искусство, а не быдлокодерство по паттернам.

Я прикладной быдлокодер и не могу понять всей глубины математических выкладок в сабже. Да я даже не могу понять о чем там вообще речь.

Ну и что хорошего. Доказано что NP задачу невозможно свести к P задаче. В результате решение NP-полных задач эвристическими методами как и ранее будет похоже на шаманство.


Сегодня обнаружил в открытом доступе новую попытку решения одной из важнейших задач теории алгоритмов — вопроса о равенстве классов сложности P и NP. Она, кстати, является одной из «проблем тысячелетия», за решение которых исследователь получает от Математического института Клэя 1 млн долл. Ещё одной такой проблемой была, например, гипотеза Пуанкаре, доказанная Григорием Перельманом.
Описание проблемы можно прочесть в Википедии (англ., рус.), а скачать доказательство — по этой ссылке.
Исследование Виная Деолаликара (Vinay Deolalikar) из лаборатории HP в Пало Альто датировано 6 августа. Можно с уверенностью утверждать, что в ближайшие несколько недель научная общественность будет усиленно искать ошибки в доказательстве.

Но то, что спустя два дня их вроде как не найдено, — уже повод для оптимизма. Например, два года назад, когда Xian-Jin Li опубликовал свою версию доказательства ещё одной «проблемы тысячеления» — гипотезы Римана, — первое указание на ошибку появилось уже на следующий день.

Ну что... Винай Деолаликар — имя звучное, годится)

Подписаться на комментарии