На днях в СМИ появилось сообщение, что индийский математик представил доказательства решения одной из задач тысячелетия. За решение каждой из них Математический институт Клэя предложил награду размером в миллион долларов, так что новость выглядит вполне сенсационной. Загвоздка в том, что и сама задача и ее решение настолько сложны, что непосвященным читателям абсолютно непонятно, что же, собственно, сделал ученый, и почему это настолько важно.
Новость о том, что сотрудник лаборатории Hewlett-Packard в Пало-Альто индиец Винэй Деолаликар (Vinay Deolalikar) написал статью, в которой сделал вывод, что классы сложности P и NP не равны, появилась в математических блогах еще в начале недели. Авторы и комментаторы этих блогов немедленно окрестили новость “сенсационной” и даже “революционной” и принялись бурно обсуждать детали доказательства и его значение для человечества. Однако официальные СМИ причем, в основном, западные, написали о Деолаликаре только сейчас. Задержка связана с тем, что среди научных журналистов не так много математиков, а без специального образования разобраться в оригинальной статье практически нереально.
В общем-то, от задачи тысячелетия сложно ожидать, что она будет легкой для понимания. Как написано на сайте института Клэя “Приз за решение задач тысячелетия призван отметить некоторые из самых сложных проблем, с которыми математики пытаются справиться на рубеже двух тысячелетий”. Раз уж сотни и даже тысячи математиков не смогли совладать с этими задачами, значит, они действительно неподъемные.
Впрочем, как раз на сайте института Клэя приведено очень доступное описание того, что же на человеческом языке означает фраза “классы сложности P и NP не равны”. Воспользуемся этим объяснением. Предположим, что перед вами стоит задача поселить студентов в общежитие, причем доступных мест всего сто, а желающих поселиться – четыреста. Кроме того, руководство спустило сверху список пар студентов, которых ни в коем случае нельзя селить вместе. Очевидно, что после того, как расселение завершено, вы можете легко проверить, были ли выполнены все условия, но вот справиться с задачей за разумное время чрезвычайно сложно – количество вариантов выбора сотни студентов из четырехсот превышает число атомов во Вселенной.
Такого рода задачи называют задачами класса сложности NP, и их очень сложно решить “в лоб” (то есть перебором всех возможных вариантов) за вменяемое время при помощи любых самых мощных суперкомпьютеров. Однако сам факт того, что задачу, правильный ответ на которую легко проверить (в нашем случае, просто сверившись с полученным от руководства списком), действительно нельзя решить в относительно короткие сроки при помощи, например, какого-нибудь хитрого алгоритма, строго не доказан. На языке математиков отсутствие такого доказательства записывается как знак вопроса в формуле "P = NP?". Как уже догадался читатель, задачи класса сложности P можно решить за адекватное время (ученые используют термин “полиномиальное время”, который означает, что время решения задачи не превосходит полинома от размера данных).
Еще один пример задачи класса сложности NP – это сборка мозаики вслепую. Вы легко можете определить, правильно ли уложены все кусочки, но вот получить, скажем, Мону Лизу из тысячи разноцветных кусочков, перебирая различные их сочетания, уже не так просто.
Впервые вопросом о равенстве или неравенстве классов сложности P и NP одновременно задались сразу два математика – Стивен Кук (Stephen Cook) и Леонид Левин в 1971 году. С тех пор ученые безуспешно пытаются на него ответить. Доказательного утверждения, можно ли все-таки поставить знак равенства между P и NP ждут не только исследователи, интересующиеся исключительно фундаментальными аспектами математики (для них вопрос является по-настоящему животрепещущим). Эта задача тысячелетия чрезвычайно важна для специалистов, занимающихся теориями компьютерных вычислений и шифрования данных.
Интерес последних, вообще-то говоря, должен разделять любой человек, который хоть раз платил за какие-то покупки в интернете своей кредитной картой. Когда вы посылаете реквизиты карты на адрес магазина, они отправляются туда в зашифрованном виде, причем чаще всего шифрование производится не по сложным схемам, о которых все мы знаем из книг о шпионах. В современных шифрах используют большие числа – передаваемая информация кодируется огромным количеством цифр (так называемый ключ), и на вскрытие этого кода злоумышленнику придется потратить столько времени, что эта задача потеряет всякий смысл.
Но – если P все-таки окажется равно NP, это означает, что злоумышленник может найти способ вскрыть шифр достаточно быстро и похитить информацию о вашей карте. Или секретные документы КГБ. Или все что угодно.
Чтобы успокоить тех, кто срочно побежал аннулировать свои карты, оговоримся, что на сегодняшний день большинство математиков полагают, что классы сложности P и NP не равны. Впрочем, эти предположения не подкреплены строгими доказательствами и основаны на опыте – до сих пор никому не удалось решить задачу класса сложности NP за полиномиальное время.
Винай Деолаликар. Фото с сайта hp.com
Доказательство Деолаликара занимает 116 страниц (здесь его можно скачать в формате pdf). Пока статья индийского математика не опубликована в рецензируемом журнале (хотя, например, статьи Григория Перельмана, за которые институт Клэя присудил ему Премию тысячелетия, так никогда и не были опубликованы), и сам он подчеркивает, что это только предварительный вариант, а окончательная версия появится чуть позже. Так что формально математики, желающие публично оценить доказательство, должны дождаться выхода готового текста. Но неформально многие из них уже начали изучать статью Деолаликара и некоторые уже выступили с критикой используемого ученым подхода.
А вот сотрудник Массачусетского технологического института (MIT) Скотт Ааронсон (Scott Aaronson) поступил иначе – он пообещал отдать Деолаликару 200 тысяч долларов, если выяснится, что его доказательство верно. Свой поступок Ааронсон мотивировал так: “Если неравенство P и NP действительно будет доказано, то моя жизнь изменится настолько кардинально, что потеря 200 тысяч будет совершенно незначима”. К этим словам трудно что-то прибавить.
Скорее всего нет("Такого рода задачи называют задачами класса сложности NP, и их нельзя решить “в лоб” (то есть перебором всех возможных вариантов) за вменяемое время при помощи любых самых мощных суперкомпьютеров),компьютер с лёгкостью выигрывает любого человека благодаря просчёту всех вариантов(шахматы-это скорее подбор нужных тактик/стратегий и защит, то есть любой может пару книжек вызубрить и сносно начать играть в шахматы), но вот китайские и японские-скорее всего да, так как ещё не один компьютер в них не преуспел.
во-первых, надо понимать разницу между проблемой в NP и NP-полной проблемой. если какая-то проблема в NP, это всего лишь значит, что для нее существует недетерминистский полиномиальный алгоритм. это вовсе не значит, что для нее нет детерминистского полиномиального алгоритма (т.е. быстрого решения методом перебора). например, простая проблема сортировки массива имеет как P-, так и NP-решения, и соответственно находится как в P так и в NP. более обще говоря, P подмножество NP. а вот т.н. NP-полные проблемы (NP-полной проблемой является такая, к которой можно свести ВСЕ другие NP-проблемы за полиномиальное время), на сегодня, не имеют детерминистски полиномиальных решений и поэтому "сложны" (если кто-нибудь таки не докажет P = NP, что, однако таки ИМХО очень маловероятно :))
но и NP-полнота еще не вечер. есть еще и ряд "более сложных" классов сложности, таких как EXPTIME, NEXPTIME, EXPSPACE, итд.
важность вопроса P != NP? однако определяется тем, что на сегодня уже известны 3000+ разных NP-полных проблем, которые, если бы кто-то доказал P = NP, все можно было бы решить "одним махом". включая очень практически (и финансово) существенные вещи как взлом public-key криптографии или проблемы производственной оптимизации :)
кроме того, никакой фундаментальной разницы между обычными шахматами и Го/Шоги нет. разница только в размере поискового пространства - в обычных шахматах оно сравнительно маленькое и с нынешним хардом может быть эффективно и быстро обыскано разными методами эвристического перебора. а вот в Го, например, оно во много раз больше (и более разветвляется, есть такой термин из теории игр) и поэтому фактически никогда не будет быстрых методов его полиномиального перебора (хотя это и не исключает создания алгоритмов, которые будут играть в Го лучше чем люди - просто эти алгоритмы должны будут быть умнее чем люди :))
Слава богу,что пока нету таких компов=)Там вроде 20+ терафлопс или сколько нужно?Делают, делают Американцы компьютер чтобы обыграть одного единственного китайца в Го=))А вообще вопрос,если разбираешься:его доказательство верно это: 1.Доказывает,что для вычисления сложных задач необходимо наращивание мощностей суперкомпов. 2.Наоборот(т.е. достаточно некого алгоритма и всё). 3.Вообще ни каким боком к этому не относится.=)?
для Го конкретное количество флопсов не играет никакой принципиальной роли :) дело в первую очередь в алгоритмах, и (уже очень вторично) в примерном порядке необходимой счетной мощности. для Го, на данный момент, алгоритмы настолько слабы, что никаких сегодняшних (да и будущих) суперкомпьютеров не хватит. более того - уже около 15 лет существует открытый приз в 2 миллиона долларов для алгоритма который выиграет у Го гроссмейстера-человека, и пока даже никаких реальных претендентов на него не было, не говоря уже о попытках выиграть.
проблема Го (в алгоритмическом плане) в том, что там слишком много вариантов. доска 19х19, и в любой стадии игры возможен ход в любую точку доски. это чрезвычайно трудно посчитать классическими эвристическими алгоритмами теории игр. сильные игроки-люди этого и не делают. они считают позицию только локально (что может делать и алгоритм), а в глобальном плане руководстуются практически не-алгоритмизируемым опытом и "общей картиной" доски. поэтому сильный игрок в Го может легко поставить "ловушку" алгоритму, зная, что тот работает только локально. наиболее многообещающие направления развития алгоритмического Го находятся в области нейронных сетей - т.е. фактически копирования метода работы человеческого мозга по распознанию форм и последовательностей. но до уровня человека-гроссмейстера в Го там еще ой как далеко. по моей оценке, пройдет еще не один десяток лет (а может и много больше), пока появятся реально конкуррентоспособные алгоритмы для Го.
> А вообще вопрос,если разбираешься
у меня диплом по информатике :) хоть моя специальность и не теория игр, но по теории сложности я сдавал теоретический экзамен, а по рандомизированным/приближенным алгоритмам вел семинары для студентов :)
> 1.Доказывает,что для вычисления сложных задач необходимо наращивание мощностей суперкомпов.
и да и нет. тут весь вопрос в том, что именно, и насколько хорошо ты хочешь считать. с одной стороны, для многих задач (аналитически нерешаемых) существуют приближенные алгоритмы, которые дают решение с какой-то степенью точности, и при этом зачастую считаемы в достаточно низкое полиномиальное время. например, хорошо известная проблема взаимодействия >=3 тел в гравитационном поле - необходимая для космических полетов - относится к этому классу). вот тут мощность компа играет большую роль - большой суперкомпьютер тут позволяет хорошо считать даже большие инстанции проблемы. например, в симуляции систем диффуравнений на больших многомерных дискретных сетках, как например при обтекании (авиакосмос, аэродинамика, потоки вообще) или метеовопросов, или подсчета как себя будут вести скажем 100 астероидов относительно друг друга, итд итп, иметь сильный комп с большой оперативной памятью очень полезно. однако, для многих других проблем нет эффективных полиномиальных алгоритмов (как например для всех NP-полных проблем), или они имеют слишком высокую степень многочлена чтобы быть реально полезными для больших инстанций проблемы (на практике это >= 4). и вот тут никакой суперкомпьютер не поможет, пока не придумаешь эффективных алгоритмов, разве что проблема сама по себе достаточно маленькая и ее можно решить тупым перебором :)
так что резюме профессионала тут выглядит примерно так - хорошо иметь сильные компьютеры, но для сложных задач надо уметь думать головой :)
> 2.Наоборот(т.е. достаточно некого алгоритма и всё).
опять, и да и нет. есть слишком много разных проблем разной степени сложности. для проблемах в P, в целом, достаточно хорошего алгоритма. компьютерный прогресс доделывает остальное. если, скажем, 30-40 лет назад считать большие (порядка 10^6 на 10^6) инстанции проблем с кубической сложностью типа, скажем, матричного умножения (т.е. скажем, расклада матриц на собственные векторы, например - что нужно для массы физических и инженерных приложений) было очень непрактично, то на сегодня это рутина и быстро делается любым домашним компом, не говоря уже о суперкомпах. а вот для NP-полных проблем ситуация в принципе никак не изменилась. приближенные алгоритмы для некоторых из них народ сделал, но в целом они как были нерешабельными для крупных инстанций, так и остаются. на этом, в частности, зиждется вся банковская и прочая криптография.
Спасибо за развёрнутый ответ, кое-что конечно не слишком вник, но в целом всё понятно.Про терафлопсы где-то читал просто,что 20+ примерная вычислительная способность мозга человека=).А так было интересно узнать просто есть ли реальный смысл в наращивании компьютерных мощностей, так как сейчас во многих наших российских университетах ставят эти суперкомпьютеры, но сами не знают, что с ними делать=))Поэтому и интересовался у вас этим вопросом.Я хоть и гуманитарий в принципе, но тяжело смотреть на людей у которых есть выкладки и интересные проекты, а им говорят финансирование не дадим всё потратили на суперкомпьютер.=)
> Про терафлопсы где-то читал просто,что 20+ примерная вычислительная способность мозга человека=)
к таким высказываниям я отношусь несколько скептически :) на практике, наша вычислительная способность в флопсах (1 флопс = 1 операция с двумя действительными числами в секунду) - примерно от нуля до трех :) это то что мы можем сознательно. а остальное - за кулисами, и мы все эти процессы никак по сути не контролируем, и оценить их на сегодня можем тоже только очень приблизительно. да, можно дать грубую оценку счетной способности мозга, если рассматривать его как крупную нейронную сеть в, скажем, 10^12 нейронов, где один нейрон работает с тактовой частотой примерно от 100 герц до килогерца... но это по сути чистый популизм. мозг - не калькулятор, и нейрон - не транзистор.. так что эти гипотетические 20 терафлопс как-то прицельно использовать никак нельзя. проблема для развития компьютеров, которые по способности решать сложные проблемы были бы на уровне человека, принципиально не в количестве операций в секунду, а в совершенно ином принципе работы, который мы пока можем только очень грубо имитировать.
> А так было интересно узнать просто есть ли реальный смысл в наращивании компьютерных мощностей
смысл есть, если есть приложения для них. а они есть. например, теорфизики или теорхимики, метеорологи, ядерщики, итд, запросто загрузят любой суперкомпьютер, какой бы мощный он не был.
> так как сейчас во многих наших российских университетах ставят эти суперкомпьютеры, но сами не знают, что с ними делать=))
ну, тут я ничего сказать не могу, т.к. живу давно не в России. но думаю, если суперкомпьютер есть, то работа для него найдется :)
это слишком невнятное утверждение. Шахматы - не проблема "сами по себе", но методами шахмат можно сформулировать много разных NP-полных проблем (например, поиск обходов доски конем является частным случаем т.н. циклов Гамильтона, NP-полной проблемы). если же речь идет только о выигрышной стратегии для шахмат, то это проблема конечного размера и поэтому принципиально неприменима для формулирования вопросов из теории сложности.
Проблема собирания картины из кусочков и расселения студентов тоже конечного размера. Если честно, не вижу, какая связь между конечность проблемы и применимости к теории сложности.
разница в том, что шахматы априори конечны. доска 8х8, 32 фигуры, любая партия решается за конечное число ходов. в принципе, все возможные партии в шахматы можно просчитать "от начала до конца" раз и навсегда, и записать в блокнотик. тогда проблема "как выиграть в шахматы" станет О(1) - т.е. решабельной за постоянное время. на любой ход противника надо будет просто открыть соответствующую страницу блокнотика и посмотреть, как из такой позиции выиграть.
проблема же со студентами бесконечна, поэтому ей можно "кодировать" (специальный термин здесь называется редукция) NP-проблемы любого размера.
Всё ещё не понимаю. Количество студентов конечно, количество комнат конечно, значит, вариантов размещения студентов по комнатам тоже конечно. Где бесконечность задачи?
разумеется, проблема со студентами тоже является NP-полной, только если она бесконечна. если она конечна, то она всего лишь одна частная NP-проблема (которая может иметь детерминистски полиномиальное решение, а может и не иметь). таких проблем однако очень много, и само по себе утверждение, что какая-то конечная проблема в NP, фактически ничего по сути дела не говорит. собирание кубика Рубика, например, тоже NP-проблема. или упомянутый паззл. или упаковка рюкзака в поход :)
фокус тут в размере поискового пространства, и существовании или отсутствии каких-то умных (полиномиальных) алгоритмов. если пространство конечное и маленькое, то мы можем "в уме" решить инстанции даже (в общем случае) NP-полных проблем - типа упаковки рюкзака - просто эвристически перебрав варианты. если пространство большое, но тоже конечное - типа как в шахматах или Го - то, хотя проблема в принципе все еще решается тупым перебором, это уже нереально на практике из-за экспоненциальных затрат во времени/пространстве. но, возможно, мы можем решить ее более умными алгоритмами которые, например, заранее отбрасывают существенную часть пространства т.к. они знают что там не будет хорошего решения. но тут уже как придется - кое-где такие алгоритмы есть, а кое-где нет. и наконец, если пространство бесконечно, то такие алгоритмы для NP-полных проблем (т.е. таких к которым можно быстро свести все остальные NP-проблемы) нам неизвестны в принципе, и скорее всего их и нет (если кто-то не докажет P = NP).
Конечно не бесконечна эта проблема т.к. кол-во студентов, комнат и рекомендаций сверху конечно. Но решение этой проблемы (не розыск одной правильной комбинации) займёт очень много времени - практически бесконечно долгое время.
П.С. термин "бесконечность" помоему в данном случае не корректен
Задачи относят к каждому из классов в соответствии с тем сколько потребуется ресурсов (например, вычислений) в зависимости от размера входных данных (в случае с собиранием картины - это число пазлов. Обозначим размер входных данных через n). Так вот: проверка верности решения (того что пазл собран верно: нужно каждый пазл сравнить с тем же местом на картине - потребуется n сравнений). А вот вопрос за какое минимальное число сравнений мы сможем собрать картину не очевиден. Если бы мы могли сказать, что число сравнений это некий многочлен (например n^2+n+3), то тогда бы эта задача была из класса P (нужно сделать всего полином вычислений от размера входных данных). Если же пытаться каждый пазл поставить на каждое место - то потребуется порядка n! (n*(n-1)*(n-2)*...*3*2*1) сравнений, что будет больше любого наперёд выбранного многочлена (степени всех переменных некие постоянные числа).
В общем мы можем говорить о принадлежности задачи к некоему классу только по отношению к размеру входных данных (в шахматах же число всевозможных расположений фигур на доске - всего лишь некое большое число - но это именно число и оно никак не может изменяться)
и кстати, NxN-обобщение шахмат не то что не в NP, а даже близко не лежало. уже по результатам 30-летней давности, даже шашки на NxN-доске EXPTIME-полны. это много сложнее чем NP. и шахматы, и Го (с японскими ко-правилами), и Шоги, обобщенные для NxN-доски, все принадлежат к этому классу. интересно, что для Го с китайскими правилами пока не показано, EXPTIME-полно оно или нет.
Насколько я понимаю, нет. P -- это задача, которая может быть решена за P(n) ходов, где n -- какая-то характерная размерность задачи (количество студентов, количество кусков мозаики, размер шахматной доски), а P(n) -- многочлен от n.
просто говоря, P != NP? спрашивает: можно ли для любой проблемы, доказательство которой можно проверить за полиномиальное (от ее размера) время, найти это доказательство за полиномиальное время?
теорема Гёделя конечно, интересный и неочевидный результат.
но на меня лично производит впечатление и тот факт, насколько большое количество важных проблем находятся именно в этой "тоненькой" прослойке между P и NP (http://en.wikipedia.org/wiki/List_of_NP-complete_problems), и как всех этих зайцев теоретически можно было бы убить одним камнем :) если бы кто-то придумал P-решение хотя бы одной из тысяч NP-полных проблем, это бы в одночасье абсолютно изменило жизнь мира.
мгновенно умерла бы почти вся криптография, например :)
Традиционные шахматы не NP. Число вариантов при имеющихся мощностях конечно... Щахматы не NP.
К традиционным шахматам интерес "уменьшился".... Придумывают другие NP.
Шахматы не показатель.Есть предметы поинтересней....
собственно говоря они и пишут: "...среди журналистов не так много математиков, а без специального образования разобраться в оригинальной статье практически нереально...")))
"Задержка связана с тем, что среди научных журналистов не так много математиков, а без специального образования разобраться в оригинальной статье практически нереально. " проблема равенства/неравенства этих классов интересует предостаточно огромное количество людей. и публикаций предостаточно, как и математиков способных оценить статью. да и сама статья не публикуется в приличном журнале без прохождения многослойного фильтра на выявление тупого и лженаучного материала представленного в статье. зачастую самым сложным является убедить именно "печатников"... так что есть кому разбираться...
другой вопрос может быть в том, что может оказаться невозможным понять что именно индус пытается сказать... ибо говорят они не наилучшим образом...
"количество вариантов выбора сотни студентов из четырехсот превышает число атомов во Вселенной." - ну и что с этого? Боитесь что вам не хватит пальцев на руках и ногах всех жителей вашей деревни? сами же пишете парой строк выше что "кроме того, руководство спустило сверху список пар студентов, которых ни в коем случае нельзя селить вместе." вот вам и будет значительное уменьшение возможных вариантов. Возможно даже не понадобится собирать всю деревню для подсчётов. всякие конкретно поставленные задачи позволяют найти путь решения не "в лоб"...
Юстас = Алексу?
На днях в СМИ появилось сообщение, что индийский математик представил доказательства решения одной из задач тысячелетия. За решение каждой из них Математический институт Клэя предложил награду размером в миллион долларов, так что новость выглядит вполне сенсационной. Загвоздка в том, что и сама задача и ее решение настолько сложны, что непосвященным читателям абсолютно непонятно, что же, собственно, сделал ученый, и почему это настолько важно.
Новость о том, что сотрудник лаборатории Hewlett-Packard в Пало-Альто индиец Винэй Деолаликар (Vinay Deolalikar) написал статью, в которой сделал вывод, что классы сложности P и NP не равны, появилась в математических блогах еще в начале недели. Авторы и комментаторы этих блогов немедленно окрестили новость “сенсационной” и даже “революционной” и принялись бурно обсуждать детали доказательства и его значение для человечества. Однако официальные СМИ причем, в основном, западные, написали о Деолаликаре только сейчас. Задержка связана с тем, что среди научных журналистов не так много математиков, а без специального образования разобраться в оригинальной статье практически нереально.
В общем-то, от задачи тысячелетия сложно ожидать, что она будет легкой для понимания. Как написано на сайте института Клэя “Приз за решение задач тысячелетия призван отметить некоторые из самых сложных проблем, с которыми математики пытаются справиться на рубеже двух тысячелетий”. Раз уж сотни и даже тысячи математиков не смогли совладать с этими задачами, значит, они действительно неподъемные.
Впрочем, как раз на сайте института Клэя приведено очень доступное описание того, что же на человеческом языке означает фраза “классы сложности P и NP не равны”. Воспользуемся этим объяснением. Предположим, что перед вами стоит задача поселить студентов в общежитие, причем доступных мест всего сто, а желающих поселиться – четыреста. Кроме того, руководство спустило сверху список пар студентов, которых ни в коем случае нельзя селить вместе. Очевидно, что после того, как расселение завершено, вы можете легко проверить, были ли выполнены все условия, но вот справиться с задачей за разумное время чрезвычайно сложно – количество вариантов выбора сотни студентов из четырехсот превышает число атомов во Вселенной.
Такого рода задачи называют задачами класса сложности NP, и их очень сложно решить “в лоб” (то есть перебором всех возможных вариантов) за вменяемое время при помощи любых самых мощных суперкомпьютеров. Однако сам факт того, что задачу, правильный ответ на которую легко проверить (в нашем случае, просто сверившись с полученным от руководства списком), действительно нельзя решить в относительно короткие сроки при помощи, например, какого-нибудь хитрого алгоритма, строго не доказан. На языке математиков отсутствие такого доказательства записывается как знак вопроса в формуле "P = NP?". Как уже догадался читатель, задачи класса сложности P можно решить за адекватное время (ученые используют термин “полиномиальное время”, который означает, что время решения задачи не превосходит полинома от размера данных).
Интерес последних, вообще-то говоря, должен разделять любой человек, который хоть раз платил за какие-то покупки в интернете своей кредитной картой. Когда вы посылаете реквизиты карты на адрес магазина, они отправляются туда в зашифрованном виде, причем чаще всего шифрование производится не по сложным схемам, о которых все мы знаем из книг о шпионах. В современных шифрах используют большие числа – передаваемая информация кодируется огромным количеством цифр (так называемый ключ), и на вскрытие этого кода злоумышленнику придется потратить столько времени, что эта задача потеряет всякий смысл.
Но – если P все-таки окажется равно NP, это означает, что злоумышленник может найти способ вскрыть шифр достаточно быстро и похитить информацию о вашей карте. Или секретные документы КГБ. Или все что угодно.
Чтобы успокоить тех, кто срочно побежал аннулировать свои карты, оговоримся, что на сегодняшний день большинство математиков полагают, что классы сложности P и NP не равны. Впрочем, эти предположения не подкреплены строгими доказательствами и основаны на опыте – до сих пор никому не удалось решить задачу класса сложности NP за полиномиальное время.
А вот сотрудник Массачусетского технологического института (MIT) Скотт Ааронсон (Scott Aaronson) поступил иначе – он пообещал отдать Деолаликару 200 тысяч долларов, если выяснится, что его доказательство верно. Свой поступок Ааронсон мотивировал так: “Если неравенство P и NP действительно будет доказано, то моя жизнь изменится настолько кардинально, что потеря 200 тысяч будет совершенно незначима”. К этим словам трудно что-то прибавить.
Шахматы -- это тоже NP?
Скорее всего нет("Такого рода задачи называют задачами класса сложности NP, и их нельзя решить “в лоб” (то есть перебором всех возможных вариантов) за вменяемое время при помощи любых самых мощных суперкомпьютеров),компьютер с лёгкостью выигрывает любого человека благодаря просчёту всех вариантов(шахматы-это скорее подбор нужных тактик/стратегий и защит, то есть любой может пару книжек вызубрить и сносно начать играть в шахматы), но вот китайские и японские-скорее всего да, так как ещё не один компьютер в них не преуспел.
тут есть несколько заблуждений :)
во-первых, надо понимать разницу между проблемой в NP и NP-полной проблемой. если какая-то проблема в NP, это всего лишь значит, что для нее существует недетерминистский полиномиальный алгоритм. это вовсе не значит, что для нее нет детерминистского полиномиального алгоритма (т.е. быстрого решения методом перебора). например, простая проблема сортировки массива имеет как P-, так и NP-решения, и соответственно находится как в P так и в NP. более обще говоря, P подмножество NP. а вот т.н. NP-полные проблемы (NP-полной проблемой является такая, к которой можно свести ВСЕ другие NP-проблемы за полиномиальное время), на сегодня, не имеют детерминистски полиномиальных решений и поэтому "сложны" (если кто-нибудь таки не докажет P = NP, что, однако таки ИМХО очень маловероятно :))
но и NP-полнота еще не вечер. есть еще и ряд "более сложных" классов сложности, таких как EXPTIME, NEXPTIME, EXPSPACE, итд.
важность вопроса P != NP? однако определяется тем, что на сегодня уже известны 3000+ разных NP-полных проблем, которые, если бы кто-то доказал P = NP, все можно было бы решить "одним махом". включая очень практически (и финансово) существенные вещи как взлом public-key криптографии или проблемы производственной оптимизации :)
кроме того, никакой фундаментальной разницы между обычными шахматами и Го/Шоги нет. разница только в размере поискового пространства - в обычных шахматах оно сравнительно маленькое и с нынешним хардом может быть эффективно и быстро обыскано разными методами эвристического перебора. а вот в Го, например, оно во много раз больше (и более разветвляется, есть такой термин из теории игр) и поэтому фактически никогда не будет быстрых методов его полиномиального перебора (хотя это и не исключает создания алгоритмов, которые будут играть в Го лучше чем люди - просто эти алгоритмы должны будут быть умнее чем люди :))
Слава богу,что пока нету таких компов=)Там вроде 20+ терафлопс или сколько нужно?Делают, делают Американцы компьютер чтобы обыграть одного единственного китайца в Го=))А вообще вопрос,если разбираешься:его доказательство верно это:
1.Доказывает,что для вычисления сложных задач необходимо наращивание мощностей суперкомпов.
2.Наоборот(т.е. достаточно некого алгоритма и всё).
3.Вообще ни каким боком к этому не относится.=)?
> Там вроде 20+ терафлопс или сколько нужно?
для Го конкретное количество флопсов не играет никакой принципиальной роли :) дело в первую очередь в алгоритмах, и (уже очень вторично) в примерном порядке необходимой счетной мощности. для Го, на данный момент, алгоритмы настолько слабы, что никаких сегодняшних (да и будущих) суперкомпьютеров не хватит. более того - уже около 15 лет существует открытый приз в 2 миллиона долларов для алгоритма который выиграет у Го гроссмейстера-человека, и пока даже никаких реальных претендентов на него не было, не говоря уже о попытках выиграть.
проблема Го (в алгоритмическом плане) в том, что там слишком много вариантов. доска 19х19, и в любой стадии игры возможен ход в любую точку доски. это чрезвычайно трудно посчитать классическими эвристическими алгоритмами теории игр. сильные игроки-люди этого и не делают. они считают позицию только локально (что может делать и алгоритм), а в глобальном плане руководстуются практически не-алгоритмизируемым опытом и "общей картиной" доски. поэтому сильный игрок в Го может легко поставить "ловушку" алгоритму, зная, что тот работает только локально. наиболее многообещающие направления развития алгоритмического Го находятся в области нейронных сетей - т.е. фактически копирования метода работы человеческого мозга по распознанию форм и последовательностей. но до уровня человека-гроссмейстера в Го там еще ой как далеко. по моей оценке, пройдет еще не один десяток лет (а может и много больше), пока появятся реально конкуррентоспособные алгоритмы для Го.
> А вообще вопрос,если разбираешься
у меня диплом по информатике :) хоть моя специальность и не теория игр, но по теории сложности я сдавал теоретический экзамен, а по рандомизированным/приближенным алгоритмам вел семинары для студентов :)
> 1.Доказывает,что для вычисления сложных задач необходимо наращивание мощностей суперкомпов.
и да и нет. тут весь вопрос в том, что именно, и насколько хорошо ты хочешь считать. с одной стороны, для многих задач (аналитически нерешаемых) существуют приближенные алгоритмы, которые дают решение с какой-то степенью точности, и при этом зачастую считаемы в достаточно низкое полиномиальное время. например, хорошо известная проблема взаимодействия >=3 тел в гравитационном поле - необходимая для космических полетов - относится к этому классу). вот тут мощность компа играет большую роль - большой суперкомпьютер тут позволяет хорошо считать даже большие инстанции проблемы. например, в симуляции систем диффуравнений на больших многомерных дискретных сетках, как например при обтекании (авиакосмос, аэродинамика, потоки вообще) или метеовопросов, или подсчета как себя будут вести скажем 100 астероидов относительно друг друга, итд итп, иметь сильный комп с большой оперативной памятью очень полезно. однако, для многих других проблем нет эффективных полиномиальных алгоритмов (как например для всех NP-полных проблем), или они имеют слишком высокую степень многочлена чтобы быть реально полезными для больших инстанций проблемы (на практике это >= 4). и вот тут никакой суперкомпьютер не поможет, пока не придумаешь эффективных алгоритмов, разве что проблема сама по себе достаточно маленькая и ее можно решить тупым перебором :)
так что резюме профессионала тут выглядит примерно так - хорошо иметь сильные компьютеры, но для сложных задач надо уметь думать головой :)
> 2.Наоборот(т.е. достаточно некого алгоритма и всё).
опять, и да и нет. есть слишком много разных проблем разной степени сложности. для проблемах в P, в целом, достаточно хорошего алгоритма. компьютерный прогресс доделывает остальное. если, скажем, 30-40 лет назад считать большие (порядка 10^6 на 10^6) инстанции проблем с кубической сложностью типа, скажем, матричного умножения (т.е. скажем, расклада матриц на собственные векторы, например - что нужно для массы физических и инженерных приложений) было очень непрактично, то на сегодня это рутина и быстро делается любым домашним компом, не говоря уже о суперкомпах. а вот для NP-полных проблем ситуация в принципе никак не изменилась. приближенные алгоритмы для некоторых из них народ сделал, но в целом они как были нерешабельными для крупных инстанций, так и остаются. на этом, в частности, зиждется вся банковская и прочая криптография.
Спасибо за развёрнутый ответ, кое-что конечно не слишком вник, но в целом всё понятно.Про терафлопсы где-то читал просто,что 20+ примерная вычислительная способность мозга человека=).А так было интересно узнать просто есть ли реальный смысл в наращивании компьютерных мощностей, так как сейчас во многих наших российских университетах ставят эти суперкомпьютеры, но сами не знают, что с ними делать=))Поэтому и интересовался у вас этим вопросом.Я хоть и гуманитарий в принципе, но тяжело смотреть на людей у которых есть выкладки и интересные проекты, а им говорят финансирование не дадим всё потратили на суперкомпьютер.=)
> Про терафлопсы где-то читал просто,что 20+ примерная вычислительная способность мозга человека=)
к таким высказываниям я отношусь несколько скептически :) на практике, наша вычислительная способность в флопсах (1 флопс = 1 операция с двумя действительными числами в секунду) - примерно от нуля до трех :) это то что мы можем сознательно. а остальное - за кулисами, и мы все эти процессы никак по сути не контролируем, и оценить их на сегодня можем тоже только очень приблизительно. да, можно дать грубую оценку счетной способности мозга, если рассматривать его как крупную нейронную сеть в, скажем, 10^12 нейронов, где один нейрон работает с тактовой частотой примерно от 100 герц до килогерца... но это по сути чистый популизм. мозг - не калькулятор, и нейрон - не транзистор.. так что эти гипотетические 20 терафлопс как-то прицельно использовать никак нельзя. проблема для развития компьютеров, которые по способности решать сложные проблемы были бы на уровне человека, принципиально не в количестве операций в секунду, а в совершенно ином принципе работы, который мы пока можем только очень грубо имитировать.
> А так было интересно узнать просто есть ли реальный смысл в наращивании компьютерных мощностей
смысл есть, если есть приложения для них. а они есть. например, теорфизики или теорхимики, метеорологи, ядерщики, итд, запросто загрузят любой суперкомпьютер, какой бы мощный он не был.
> так как сейчас во многих наших российских университетах ставят эти суперкомпьютеры, но сами не знают, что с ними делать=))
ну, тут я ничего сказать не могу, т.к. живу давно не в России. но думаю, если суперкомпьютер есть, то работа для него найдется :)
Шахматы на бесконечной доске :)
это слишком невнятное утверждение. Шахматы - не проблема "сами по себе", но методами шахмат можно сформулировать много разных NP-полных проблем (например, поиск обходов доски конем является частным случаем т.н. циклов Гамильтона, NP-полной проблемы). если же речь идет только о выигрышной стратегии для шахмат, то это проблема конечного размера и поэтому принципиально неприменима для формулирования вопросов из теории сложности.
Проблема собирания картины из кусочков и расселения студентов тоже конечного размера. Если честно, не вижу, какая связь между конечность проблемы и применимости к теории сложности.
Собственно, нашёл, что таки NP, см. ниже
разница в том, что шахматы априори конечны. доска 8х8, 32 фигуры, любая партия решается за конечное число ходов. в принципе, все возможные партии в шахматы можно просчитать "от начала до конца" раз и навсегда, и записать в блокнотик. тогда проблема "как выиграть в шахматы" станет О(1) - т.е. решабельной за постоянное время. на любой ход противника надо будет просто открыть соответствующую страницу блокнотика и посмотреть, как из такой позиции выиграть.
проблема же со студентами бесконечна, поэтому ей можно "кодировать" (специальный термин здесь называется редукция) NP-проблемы любого размера.
Всё ещё не понимаю. Количество студентов конечно, количество комнат конечно, значит, вариантов размещения студентов по комнатам тоже конечно. Где бесконечность задачи?
разумеется, проблема со студентами тоже является NP-полной, только если она бесконечна. если она конечна, то она всего лишь одна частная NP-проблема (которая может иметь детерминистски полиномиальное решение, а может и не иметь). таких проблем однако очень много, и само по себе утверждение, что какая-то конечная проблема в NP, фактически ничего по сути дела не говорит. собирание кубика Рубика, например, тоже NP-проблема. или упомянутый паззл. или упаковка рюкзака в поход :)
фокус тут в размере поискового пространства, и существовании или отсутствии каких-то умных (полиномиальных) алгоритмов. если пространство конечное и маленькое, то мы можем "в уме" решить инстанции даже (в общем случае) NP-полных проблем - типа упаковки рюкзака - просто эвристически перебрав варианты. если пространство большое, но тоже конечное - типа как в шахматах или Го - то, хотя проблема в принципе все еще решается тупым перебором, это уже нереально на практике из-за экспоненциальных затрат во времени/пространстве. но, возможно, мы можем решить ее более умными алгоритмами которые, например, заранее отбрасывают существенную часть пространства т.к. они знают что там не будет хорошего решения. но тут уже как придется - кое-где такие алгоритмы есть, а кое-где нет. и наконец, если пространство бесконечно, то такие алгоритмы для NP-полных проблем (т.е. таких к которым можно быстро свести все остальные NP-проблемы) нам неизвестны в принципе, и скорее всего их и нет (если кто-то не докажет P = NP).
Конечно не бесконечна эта проблема т.к. кол-во студентов, комнат и рекомендаций сверху конечно. Но решение этой проблемы (не розыск одной правильной комбинации) займёт очень много времени - практически бесконечно долгое время.
П.С. термин "бесконечность" помоему в данном случае не корректен
компьютеры создаваемые для игры в шахматы против человека пока что работают именно перебирая возможные комбинации.
Deep Blue : ability to analyze about 300,000,000 board positions on it's decision tree
Гарик Каспаров : as he said, "less than one"
Задачи относят к каждому из классов в соответствии с тем сколько потребуется ресурсов (например, вычислений) в зависимости от размера входных данных (в случае с собиранием картины - это число пазлов. Обозначим размер входных данных через n). Так вот: проверка верности решения (того что пазл собран верно: нужно каждый пазл сравнить с тем же местом на картине - потребуется n сравнений). А вот вопрос за какое минимальное число сравнений мы сможем собрать картину не очевиден. Если бы мы могли сказать, что число сравнений это некий многочлен (например n^2+n+3), то тогда бы эта задача была из класса P (нужно сделать всего полином вычислений от размера входных данных). Если же пытаться каждый пазл поставить на каждое место - то потребуется порядка n! (n*(n-1)*(n-2)*...*3*2*1) сравнений, что будет больше любого наперёд выбранного многочлена (степени всех переменных некие постоянные числа).
В общем мы можем говорить о принадлежности задачи к некоему классу только по отношению к размеру входных данных (в шахматах же число всевозможных расположений фигур на доске - всего лишь некое большое число - но это именно число и оно никак не может изменяться)
таки NP
http://en.wikipedia.org/wiki/P_versus_NP_problem#Still_harder_problems
"шахматы" NxN - это не шахматы, а всего лишь что-то похожее на шахматы :)
и кстати, NxN-обобщение шахмат не то что не в NP, а даже близко не лежало. уже по результатам 30-летней давности, даже шашки на NxN-доске EXPTIME-полны. это много сложнее чем NP. и шахматы, и Го (с японскими ко-правилами), и Шоги, обобщенные для NxN-доски, все принадлежат к этому классу. интересно, что для Го с китайскими правилами пока не показано, EXPTIME-полно оно или нет.
Объясните чайнику, эта задача тоже самое или нет:
Так ли легко доказать прямое утверждение, как и обратное?
Не связано ли оно с доказательством от противного?
Насколько я понимаю, нет. P -- это задача, которая может быть решена за P(n) ходов, где n -- какая-то характерная размерность задачи (количество студентов, количество кусков мозаики, размер шахматной доски), а P(n) -- многочлен от n.
нет, это не имеет ничего общего с P или NP.
просто говоря, P != NP? спрашивает: можно ли для любой проблемы, доказательство которой можно проверить за полиномиальное (от ее размера) время, найти это доказательство за полиномиальное время?
Ну, ладно..
Тогда меня больше возбуждает теорема Гёделя :-)
теорема Гёделя конечно, интересный и неочевидный результат.
но на меня лично производит впечатление и тот факт, насколько большое количество важных проблем находятся именно в этой "тоненькой" прослойке между P и NP (http://en.wikipedia.org/wiki/List_of_NP-complete_problems), и как всех этих зайцев теоретически можно было бы убить одним камнем :) если бы кто-то придумал P-решение хотя бы одной из тысяч NP-полных проблем, это бы в одночасье абсолютно изменило жизнь мира.
мгновенно умерла бы почти вся криптография, например :)
опираясь на примеры с картами . . .. как-бы ВСЕ очевидно, тока вот как доказать ХЗ.
нада еще раз товарища перечитать, и понятьт как он с помощю математики доказал что 2 события НЕ СВЯЗАНЫ.
Традиционные шахматы не NP. Число вариантов при имеющихся мощностях конечно... Щахматы не NP.
К традиционным шахматам интерес "уменьшился".... Придумывают другие NP.
Шахматы не показатель.Есть предметы поинтересней....
какие-то они медленные на ленте - ещё пару дней назад в этом доказательстве нашли ошибки.
собственно говоря они и пишут:
"...среди журналистов не так много математиков, а без специального образования разобраться в оригинальной статье практически нереально...")))
дена
"Задержка связана с тем, что среди научных журналистов не так много математиков, а без специального образования разобраться в оригинальной статье практически нереально. "
проблема равенства/неравенства этих классов интересует предостаточно огромное количество людей.
и публикаций предостаточно, как и математиков способных оценить статью.
да и сама статья не публикуется в приличном журнале без прохождения многослойного фильтра на выявление тупого и лженаучного материала представленного в статье.
зачастую самым сложным является убедить именно "печатников"...
так что есть кому разбираться...
другой вопрос может быть в том, что может оказаться невозможным понять что именно индус пытается сказать... ибо говорят они не наилучшим образом...
"количество вариантов выбора сотни студентов из четырехсот превышает число атомов во Вселенной." - ну и что с этого? Боитесь что вам не хватит пальцев на руках и ногах всех жителей вашей деревни?
сами же пишете парой строк выше что "кроме того, руководство спустило сверху список пар студентов, которых ни в коем случае нельзя селить вместе."
вот вам и будет значительное уменьшение возможных вариантов. Возможно даже не понадобится собирать всю деревню для подсчётов.
всякие конкретно поставленные задачи позволяют найти путь решения не "в лоб"...