P vs NP — неужто проблема решена?!
вон оно че: www.hpl.hp.com/...apers/pnp_preliminary.pdf
некто из Аш-Пи Лабс полагает, что решил Проблему Тысячелетия.
какие у кого интуитивные предположения на этот счет? прав мужык, аль нет?
обсуждаем.
Facebook
Twitter
LinkedIn
anonymous
Хм, а вот история учит, что они не только шахматы придумали... en.wikipedia.org/...ian_mathematics
математика (как точная наука) и индусы — вещи несовместимые.
ставлю 10 баксов что индус обломается.
статьи на Сапфире нет, это конференция для партнеров/клиентов, там всякие презентации. в одной из них Платтнер и рассказывал о применении кол.БД в их разработках. Вот ссылка: презентация Вишаля Сикки и Хассо Платтнера тебя кинет на логин форму, а после логина на сам ролик. Должно работать. Платтнер выступает после Вишаля. Но советую посмотреть все (хоть у Вишаля и характернейший акцентик: -)) В самом начале симпатичный ролик для красоты.Я видел этот сайт и даже зарегестрировался там, но статьи про колонко ориентированные базы данных там сверху не лежат к сожалению.
Но есть и статья. Есть на Ей-Си-Ем, но платно конечно. Но есть и бесплатная: A Common Database Approach for OLTP and OLAP Using an In-Memory Column Database
Сашко
что то я суть потерял — скажем что, сложно было в НИИ устроиться, считаться научным сотрудником, и работать якобы над какими то теоретическими или практическими проблемами? Врядли. Просто ЗП низкая, перспектив мало и это отпугивает...
Один только факультет знаю в Украине, откуда могут еще выйти серьезные математики — это физмат КПИ. Не знаю как там сейчас, но раньше туда шли талантливые ребята — призеры международных олимпиад по математике и физике, учиться там было тяжело и выпускники шли работать в R& D.а многие профессии слишком сложны, чтоб там было много людей. не зависимо от спроса. скажем физик-теоретик и т.п.
Та же прикладная математика КПИ — раньше (при СССР) выпускники шли работать в НИИ сражаться с ЕС ЭВМ, получали повышенную ЗП сразу же как младшие научные сотрудники. Сейчас — из моей группы только одного знаю что пошел работать и как то математику применяет, остальные кто куда.
crypto5
подскажу, хотя особо шастать и не надо: -) при запросе «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 Сергей Волошин
Должна быть гласность в математике и не должно быть демократии
Sergii Voloshyn
P vs. NP: суета вокруг дивана
А по каким материкам шагают эти колоночные БД, что я о них первый раз слышу?
Можно линки примеров коммерческого использования?
А бывают б... плохие математики или теоретические физики? Ну такие, которые всю жизнь работали, получали какие-то гранты, а так ничего и не открыли и не изобрели. Вы их уважаете так же как и «джава-кодерков» или больше?
Вы не поверите, но колоночные базы данных исследуются в институте Хассо Платтнера, недавними аспирантами, абы потом эти наработки воплотить в жизнь в трендовом SAPe.
Прикольно, то есть колоночные БД уже много лет шагают по земле (у того же Оракла в том числе), а академия только проснулась?
мы все верим вашему опыту. но, вы не поверите: когда-то давно некто Эдгар Франк Кодд (сумасшедший ученый, живущий на гос.подаяние?!) создал реляционную модель данных
Жесть, ниче что Код работал в IBM, и до его статьи у IBM уже была MicroDBMS, реализующая реляционную модель? И конечно же никаких P и NP там не было...
> то уже завтра мы бы имели на выходе 100500 математиков на любой вкус и цвет.
это количество дворников\грузчиков\жавакодеров диктуется спросом.,
это количество дворников\грузчиков\жавакодеров диктуется спросом.,
а многие профессии слишком сложны, чтоб там было много людей. не зависимо от спроса. скажем физик-теоретик и т.п.
Вы так говорите, как будто в этом что-то плохое. Вот чем вам, высокоуважаемый, не понравились джаво кдерки? Ну не все они безусловно д’артаньяны, но тоже самое можно сказать про любую отрасль.А джава-кодерков туда не допустят.
И смею вас заверить, что если бы знания математики были так же востребованы как жава/дотнето кодеризм, то уже завтра мы бы имели на выходе 100500 математиков на любой вкус и цвет.
Alexandr Gavriluk
проджектменеджер 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? »: хотите вы того или нет, но теоретические основы вычислений были, есть и будут основой основ. Независимо от красивых «трендов индустрии».
сторонникам подхода «Кому вообще нужны эти P и NP? »: хотите вы того или нет, но теоретические основы вычислений были, есть и будут основой основ. Независимо от красивых «трендов индустрии».
и, уважаемейший проджектменеджер, я хотел бы предостеречь вас от снисходительного отношения к «недавним аспирантам» и фетишизма относительно «трендовых» ораклов.
но поверьте уж моему опыту
мы все верим вашему опыту. но, вы не поверите: когда-то давно некто Эдгар Франк Кодд (сумасшедший ученый, живущий на гос.подаяние?!) создал реляционную модель данных. И именно его статья вдохновила Ларри Эллисона на создание горячо любимого вами Оракла. Вы, простите, приблизительно представляете о чем речь? А сколько «трендовых» словечек в той статье? Вы не поверите, но колоночные базы данных исследуются в институте Хассо Платтнера, недавними аспирантами, абы потом эти наработки воплотить в жизнь в трендовом SAPe. Абы вы потом рассказали нам всем, сколько прозы в проектах по разработке Оракл. Да-да.
Если ваше представление об IT сводится исключительно к системам управления складом и логистикой, могу лишь сожалеть. В мире делается очень много интересных проэктов в том числе и в области ИИ, и в том числе ИИ для управления автомобилем ec.europa.eu/...08_04_01_en.htm
Корпоративные системы тоже часто отличаются повышенной сложностью, высокими нагрузками, и большой степенью ответственности, так как там обрабатываются миллиарды долларов. А еще пишутся операционные системы, делаются инфраструктуры cloud computing, пишутся специализированные и общего назначения базы данных, создаются новые роботизированные устройства. Мне кажется вы сильно преувеличиваете.
2Soft могут
www.youtube.com/watch v=5u4G23_OohI& feature=channel
проджектменеджер 1 час назадИ написать ышшо один Склад-2010. Проблема IT в том, что она уже неспособна создать ничего нового, все псевдоновое ремейк старых технологий. Поэтому и для большинства задач достаточно или готового Опенсоурса или Excel. А новых задач для решения на старых технологиях становится всё меньше и меньше.
ну не всем же формы шлепать да и хмл-ки править.
Да что вы говорите? Кому вообще нужны эти P и NP? Только кучке сумасшедших ученых, которые живут на гос. подаяния. Смотрите на тренды идустрии, учите Oracle,.NET, Java EE, SAP, и вам не прийдется сублимировать ваши жизненные неурядицы в псевдонаучных дискусиях!
Во к примеру, насколько сложно написать автоводителя транспорта, чтобы он полностью заменил человека? Ведь мощности компьютера это уже позволяют, просто специалистов нет. И часть библиотек даже есть (построение трехмерного изображения по двум двухмерным).
А на новые «Склады» деньги выделят разве что для получения откатов.
Во первых я вам не деточка, во вторых, можно подумать что от осознания что 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
картинка слева.отвечает на твой вопрос?
Очевидно же что не отвечает!
> плюс мильён
ну не всем же формы шлепать да и хмл-ки править.
crypto5
upload.wikimedia.org/...ity_classes.svg
и
upload.wikimedia.org/...ete_np-hard.svg
картинка слева.
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 опубликовал свою версию доказательства ещё одной «проблемы тысячеления» — гипотезы Римана, — первое указание на ошибку появилось уже на следующий день.
Ну что... Винай Деолаликар — имя звучное, годится)
65 коментарів
Додати коментар Підписатись на коментаріВідписатись від коментарів