воскресенье, 27 июля 2008
В конце прошлой записи мы вплотную подошли к проблеме равенства классов сложности P и NP. Сформулировать ее можно следующим образом:
Если правильность ответа на какой-либо вопрос можно проверить за полиномиальное время, то верно ли, что этот ответ возможно так же быстро найти (т.е. за полиномиальное время и используя полиномиальную память)?читать дальшеПроблема Кука (P=?NP) ждет своего разрешения уже 37 лет. Интуитивно, вроде бы ясно, что эти классы ну никак не могут быть равны. И сейчас (поскольку никто не может доказать их равенство) все ведут себя так, как будто они и неравны.
Из определения классов Р и NP (напомню, класс Р состоит из задач, разрешимых за полиномиальное время; класс NP состоит из задач, которые разрешимы с подсказкой за это же полиномиальное время) следует, что P ⊂ NP.
Т.е. если мы представим это в виде картинки, получим следующее:

P ⊂ NP
Однако до сих пор никто не может ни доказать, ни опровергнуть строгость этого включения, иными словами, найти такой алгоритм, который лежит в классе NP, но не принадлежит в P (т.е. находится в желтой части картинки).
Давайте посмотрим на NP-полные задачи.
Из определений классов следует, что класс Р — класс самых легких задач из NP. Класс NP-полных задач — самый сложный. NP-полные задачи решаются за экспоненциальное время, а это может быть очень, очень долго!
NPC ⊂ NP (где NPC — NP-Complete — NP-полные задачи)
На картинке классы Р и NPC не пересекаются:
NPC ∩ P = ∅
А что бы было, если бы они пересеклись? По определению NP-полной задачи к ней можно свести любую задачу из класса NP. Поэтому если хотя бы для одной из них удастся найти алгоритм решения за полиномиальное время — это будет означать: УРА! Проблема решена!
"Ура", да не очень "ура"!
Потому что если человечество научится быстро (за полиномиальное время) решать NP-полные задачи, последствия будут очень и очень печальными.
Практическая криптография (по большей части) окажется бесполезной. Вся защищенная информация окажется полностью "беззащитной". Заходи, кто хочешь, бери, что хочешь!
Кроме этого, теория алгоритмической сложности испытает очень существенные потрясения. Потому что есть еще много-много разных классов, о которых я здесь просто не упоминала, но часть из них образует (бесконечную) иерархию внутри NP. Если же равенство P=NP будет доказано, вся эта иерархия свернется в один единственный класс Р.
Однако же, я думаю, выгоды тоже будут колоссальными! Мы научимся считать быстро! Всё!
А вот повторю то, о чем писала в прошлый раз:
Проблема равенства классов P и NP является одной из семи проблем, за решение которых Математический институт Клэя назначил премию в 1 млн. долларов США.
Кстати, на сайте этого института дано уморительное описание этой проблемы!
www.claymath.org/millennium/P_vs_NP/
Не поленюсь даже и переведу. (Хотя за точность перевода ручаться не буду)
***
Предположим, вы организуете расселение четырехсот студентов университета. Однако (как всегда) общежитие не может вместить всех, и места в этом общежитии получат только сто из них. Чтобы усложнить вашу задачу, декан выдал вам список пар "несовместимых студентов" и потребовал, чтобы ни одна пара из этого списка не оказалась вместе!
Это пример того, что ученые называют NP-задачей, т.к. легко проверить, является ли определенный выбор ста студентов подходящим (т.е. ни одна пара из результирующего списка не оказалась в списке, выданном деканом), однако задача формирования такого списка с нуля кажется настолько трудной, что выполнить ее практически невозможно.
В самом деле, общее число путей выбора ста студентов из четырехсот кандидатов больше чем число атомов в нашей Вселенной! (прим. АР: неужели правда? С400100 — больше, чем число атомов Вселенной? Хотя что это я... Если всего-то до миллиарда можно считать больше 30 лет...)
Таким образом никакая цивилизация будущего не может даже надеяться на создание суперкомпьютера, способного решить эту задачу с помощью "грубой силы" )))), т.е. проверяя каждую возможную комбинацию 100 студентов из 400. Однако эта очевидная трудность может всего лишь отражать недостаток изобретательности вашего программиста ))))
Фактически, это одна из выдающихся проблем информатики — доказать существование или несуществование такого вопроса, ответ на который можно легко проверить, но который требует невероятно долгого времени для своего решения любым прямым методом.
Задачи, аналогичные той, которую мы рассмотрели, точно кажутся именно такими! Но однако до сих пор никто не смог доказать, что хотя бы одна из них, на самом деле настолько сложна, как кажется! Т.е. что на самом деле нет ни одного возможного способа получить ответ с помощью компьютера. Стивен Кук и Леонид Левин сформулировали проблему Р (т.е. легко найти) vs NP (т.е. легко проверить) независимо друг от друга в 1971 г.
(Конец цитаты)
Так что если кто-то таки найдет доказательство равенства этих классов, смело сможет расселять студентов по общежитиям)))
А на самом деле, всё-таки, надо полагать, кроме огромного минуса в виде полного кризиса в области защиты данных, человечество получит и грандиозный плюс! Решать быстро задачи такого класса сложности — оооо, этим надо гордиться! Только вот что-то расправляться с этой проблемой никто не торопится...
@темы:
Алгоритмы,
Искусственный интеллект,
Поп-математика,
Amicus Plato
Большое спасибо за такой чудесный цикл статей!!!
Это такой огромный труд!
(может тебе это где-нибудь издать? В каком-нибудь научном или научно-популярном издании. Потому что аналогов этому нет и не будет)
да ну, брось! ))))
это же почти всё компиляция известных фактов! ))))
моих заслуг тут практически никаких)
А вообще: спасибо тебе большое!
большое спасибо. )
clique-problem.narod.ru
clique-problem.narod.ru/clique.pdf
Алгоритм полиномиальный.
спасибо за ссылки!
P.S.
"Стивен Кук и Леонид Левин сформулировали проблему Р (т.е. легко найти) vs NP (т.е. легко проверить) независимо друг от друга в 1971 г."
Кук - 1971
Левин (независимо) - 1973
Карп (1972) - предположил символы P и NP
Интересно: www.timescube.com
спасибо за поправки.
Вы бы подписывались как-то, если не сложно, а то даже не совсем понятно, вы один человек, или все "гости" здесь разные.
Действительно, интересно! Спасибо!
Sensile, погляди на ссылку!
Интересно, институт Клэя хочет получить решение проблемы Кука или задачи о расселении, как Вы думаете?
Доказательство.
Богданов-Бельский на своей картине "Устный счёт" привёл выражение (10^2+11^2+12^2+13^2+14^2)/365, величину которого ученики церковно-приходской школы должны вычислить в уме.
Решение.
1. Так как найти значение выражения предлагается найти ученикам ЦПШ, да ещё и устно, уместно предположить, что оно целое.
2. Числитель заведомо больше 365=365х1 и заведомо меньше 1095=365х3.
Следовательно, ответ есть 2. Время счёта - менее 5 секунд.
Уверен, что проверить его быстрее нельзя.
Что, "проблема" решена?
Так какова же правильная формулировка проблемы Кука?.
8524* 7659=9. Как я знал это, ещё не зная, что
8524*7659= 65 285 316=6+5+2+8+5+3+1+6=36=3+6=9
Всё просто 8524=8+5+2+4=19=1+9=10=1+0=1 т.е. N=1 далее
7659=7+6+5+9=27=2+7=9 т.е. P=9 далее 1*9=9 всё проверка произведена и сделано это раньше, чем я приступил к решению задачи. "Информация, необходимая для проверки положительного ответа называется сертификатом ". Из предложенного алгоритма следует, подобрать цифры в числах легко, арифметика она и есть арифметика. Чтобы узнать что 8524=1, ума потребуется не слишком много и это меня радует, ниже я объясню почему. Пример, приведённый выше, это так сказать, классика т.е. 1*9=9, т.е. P=P. Логично будет задать вопрос, как работает этот алгоритм, когда например N#1, а равно например 7, т.е. изменяем к примеру последнюю цифру в числе 8524, т.е. проще говоря было 8524, а стало 8521, тогда разумеется N будет равно 7. Проверим 8521=8+5+2+1=16=1+6=7, далее решим с этим N = 8521=7 задачу получения P, как говорится в той части где NP, т.е. имея N=7, и как мы помним, что P осталось прежним, т.е. равным 9, перемножаем 7 и 9, получаем естественно 63, далее нужно сделать последний шаг, так как у нас получилось двухзначное число 63. Т.е. нужно сложить цифры 6 и 3, получаемая цифра 9 - окончательный ответ. Проверим, как говорится, на всякий случай.
8521*7659=65 262 339 =6+5+2+6+2+3+3+9=36=3+6=9 опять получилось, как и в предыдущем примере 9=9. Ну тут уж ничего не поделаешь, таблицу умножения ещё никто не отменял 7*9=63. Похоже на то, что если менять цифры в N, то всегда будет 9, и в той части где NP, и где P. Но нам никто ведь не сказал, что нельзя менять цифры и в P где NP. Что мы и сделаем, оставим N равным 8521 =7, изменим P, сделаем его равным 8, т.е. было
7659, стало 7658, проверим, так ли это? 7658=7+6+5+8=26=2+6=8, да, это так. Получим решение 8521*7658 =? Но не для нас, мы ведь знаем алгоритм, мы уже помним о том, что 8521=7, а 7658=8, т.е.
N= 7, а P=8, перемножим их, получим естественно 56, далее делаем предпоследний шаг для полученного числа 56=5+6=11, а вот теперь последний шаг 11=1+1=2. Проверим так ли это?
8521*7658= 65 253 818 =6+5+2+5+3+8+1+8=38=3+8=11=1+1=2 проверка показала, да, действительно ответ был правильным, ну тут уж никуда не денешься, математика, как известно, наука точная.
—
Николай Иванович ШИРЯЕВ
..ответить
Вт, 01/11/2011 - 20:04 — Н.И.Ширяев Практическое применение этого алгоритма .
В начале хочу обратить ваше внимание на то , что 1=1 ; 2=2; 3=3; 4=4;
5=5; 6=6; 7=7; 8=8; 9=9 .И ещё на ряд фактов говорящих о том , что
1#2; 1#3; 1#4;1#5; 1#6; 1#7; 1#8; 1#9 ;
2#3; 2#4; 2#5; 2#6; 2#7; 2#8; 2#9;
3#4; 3#5; 3#6; 3#7; 3#8; 3#9;
4#5; 4#6; 4#7; 4#8; 4#9;
5#6; 5#7; 5#8; 5#9;
6#7; 6#8; 6#9;
7#8; 7#9;
8#9 .
Т.е. перед нами предстал ряд пар цифр равных друг другу их 9 пар как мы видим . И ряд пар цифр не равных друг другу их 36 пар и мы тоже это видим .
Нам ни что и ни кто не мешает назвать пары цифр равных друг другу , назвать совместимыми друг с другом . И пары цифр не равных друг другу , не совместимых друг с другом . Позже мы поймём почему мы так сделали .
«список пар "несовместимых студентов" и потребовал, чтобы ни одна пара из этого списка не оказалась вместе!»
Мы имеем список пар несовместимых студентов их ровно 36 пар . Так же мы имеем список пар совместимых студентов их этих пар ровно 9 , что я под этим подразумеваю я показал выше в начале этого своёго комментария , так же я покажу ниже этого своего объяснения говорящему нам ,( как практически применять этот алгоритм ), что я под этим подразумеваю .
Имеем ли мы 400 студентов желающих занять место в общежитии ? Ответ – да мы имеем 400 студентов желающих занять место для своего проживания в нём . Но мы также знаем о том , что мест свободных в нём ( в этом общежитии ) только 100 .Только один из четырёх согласно имеющимся данным может там проживать .
Список пар несовместимых студентов, данный деканом, не усложняет задачу выбора одного студента из четырёх а облегчает её . Каким именно образом будет показано ниже . Список пар несовместимых студентов является в данной ситуации своеобразной уловкой для стимулирования процесса к развитию сознания студента . Поэтому в этой задаче данной деканом и не сказано , что такое представляет собой этот список , можно только сделать предположение , что под несовместимостью студентов предполагается психологическая несовместимость . Впрочем сколько людей столько и мнений , но не в этом как говорится суть . А суть в том , что этот список пар, несовместимых пар студентов подразумевает наличие существования списка пар совместимых студентов .Как же иначе , одно без другого не имеет под собой никакого разумного основания для дальнейшего размышления .
Желание каждого из 400 студентов ( проживать в общежитии) будет как мы увидим из дальнейшего повествования , является невозможностью отказа каждого из этих студентов для следующей процедуры действий .Во – первых :каждому из студентов будет предложено взять со стола 2 карты , по своему выбору любые но только 2 . Всего на столе будет лежать 9 карт ( или карточек ) перед каждым из студентов . Как вы сами понимаете с одной стороны карточки нет никаких знаков указывающих студентам на то какая цифра от 1 до 9 изображена на другой стороне карточки .
Как только все желающие студенты согласились с этой нехитрой и не сложной процедурой , но и также с очерёдностью подхода к столу , которая разумеется разыграна будет перед этим подходом к столу, за двумя карточками .( Как разыграть очерёдность подхода к столу и для чего это нужно мы увидим в дальнейших комментариях ).
Во – вторых : после того как студент взял со стола две любые по его желанию из девяти .Он их ,(которые взял) , показывает остальным 399 студентам .Допустим первый студент взял со стола две карточки на обратной стороне которых цифры , на одной из них цифра 1 на другой цифра 5 .Т.е. фиксация того факта , что первый студент сам своими руками взял со стола две карточки из лежащих там девяти карточек произошла .Т.е. фиксация сознанием всех 400 студентов одновременно ( при современных средствах передачи информации сделать это совсем несложно ) . Т.е и тем кто брал и теми кто наблюдал за этим событием .Возможность того , что на столе остались только карточки с цифрами 2 , 3 ,4 , 6 , 7 , 8 , 9 проверить предоставляется , разумеется как и первому студенту так последующим 399 , почему бы нет когда очень даже да . Кто –то её эту возможность будет использовать кто-то нет , но не в этом суть . А суть в том , чтобы был произведён выбор 100 студентов из 400 максимально честно и справедливо .
В –третьих : и первый студент и остальные 399 студентов делают запись у себя на листе бумаги –студент под номером 1 взял со стола карточки с цифрами 1 и 5 , в результате этого факта все 400 студентов произвели следующие действия 1+5 , и убедились в том, что сумма этих цифр равна 6 . Сделать у себя запись на листе бумаги так - 1). 1+5=6 совсем не сложно . Вы поймёте ниже почему я так подробно расписываю всю эту процедуру . Немного как говорится терпения .
В четвёртых :к столу согласно очереди подходят все остальные 399 студентов .После подхода каждого из студентов список становится разумеется всё длиннее и длиннее .Но не в этом как говорится суть . Суть в том , как складывать между собой цифры и что , какой иметь результат в результате сложения этих двух цифр .Смею надеяться на то , что эти студенты которые участвуют в данной процедуре описанной только , что выше, знакомы с тем какие я привёл доказательства равенства математических классов NP=P .В результате этого знания , если допустим студент идущий по очереди четвёртый возьмёт из 9 карт две и одной из них будет цифра 2 а на другой цифра 9 , то он без тени сомнения знает , что 2+9=2 т.к. он повторяю уже знаком с тем фактом , что 2+9=11 а 11=1+1=2.
В пятых : этот четвёртый студент самим фактом взятия со стола карточек им же , с цифрами 2 и 9 попадает в список пар совместимых студентов .Далее я подробно объясню почему это так .А пока я предлагаю посмотреть вам на следующую картину 2+9=2 и ещё на другую картину 2=2 , т.е. убирая в первой картине 2+9=2 , два знака + и цифру 9 мы имеем вторую картину 2=2 .Как мы видим у первого студента дела сложились не столь прекрасно как у четвёртого 1+5=6 – первая картина , и 1#6 вторая картина , после изъятия из первой картины 1+5=6 , знака + и цифры 5 , знак равенства во второй картине не может остаться прежним = он меняется на противоположный # ( не равно ) .
В шестых :привожу список с результатом выхода каждого студента ( роль каждого из 400 студентов в данном списке выполнял я вместе со своим младшим сыном ) .Получилась вот такая картина , в которой хотелось бы отметить , что первой цифрой в той части где цифры складываются должна быть цифра меньше чем вторая т.е. 1+6 , но никак не 6+1 и так далее и тому подобное как говорится .
1).1+5=6; 2).1+7=8; 3).1+6=7; 4).2+9=2; 5).2+5=7; 6).2+3=5; 7).1+8=9; 8).2+4=6; 9).3+4=7; 10).4+5=9; 11).5+9=5; 12).4+7=2; 13).7+9=7; 14).3+8=2; 15).3+6=9; 16).1+9=1; 17).4+7=2; 18).1+3=4; 19).2+5=7; 20).6+9=6; 21).8+9=8; 22).3+5=8; 23).1+4=5; 24).3+5=8; 25).6+9=6;
вся информация связанная с этой проблемой находится на сайте: centr.skravchenko.ru/index.htm/node/490
и дальнейшее её развитие.
Я не хочу здесь публиковать полностью список с результатами действия подхода остальных студентов , не в этом как говорится суть .Хочу лишь только сказать о том , что тот студент у которого одна из карточек которую он возьмёт окажется с цифрой 9 окажется более вероятным кандидатом для проживания в общежитии . Т.к. 100% вероятность зависит от очерёдности подхода к столу . Вероятность того , что у первых 100 (ста) студентов , у каждого с первого по сотого из двух карточек одна окажется с цифрой 9 не исключается . В том списке который я закончил в предыдущем комментарии на 25 студенте , получилось так что 92 студента из 400 взяли со стола две карточки и одна из них была цифра 9 . И этих 92 студентов можно сразу же формировать , кто с кем будет жить . Данные о том , что именно студенты под номерами 16, 51 , 143 , 237 , 278 , 309 , 319 , 337 , 361 и 387 взяли со стола две карточки одна из которых была с цифрой 1 а другая с цифрой 9 - есть . И здесь уже не имеет значения кто с кем в комнате будет жить ( эти 10 студентов ) т.к. в условии задачи об этом не говорилось , хотя и это тоже можно решить с помощью математики , почему бы и нет .
Так же мне не хочется приводить здесь данные своих виртуальных студентов , о том какие ( и сколько из них ) взяли со стола карточки с цифрами 2 и 9 , 3 и 9 , 4 и 9 , 5 и 9 , 6 и 9 , 7 и 9 , 8 и 9 - не в этом как говорится суть . Суть как говорится дальше по ходу текста .
Как мы видим осталось 8 мест, и для 308 студентов будет проведён второй тур . И так до тех пор пока согласно условию задачи только 100 студентов займут места для проживания в общежитии .Я не думаю что это займет много времени . Второй тур будет гораздо короче первого 8 мест 308 желающих .Возможно не только благодаря тем данным , которые я имею перед собой .
Т.к. в первом туре , первые 8 студентов из первых 31 студентов взяли со стола две карточки , одна из которых оказалась с цифрой 9 . Чтобы знать как будут обстоять ваши дела с расселением ваших виртуальных или ваших реальных студентов вам разумеется нужно самим попробовать как действует этот метод в котором, за основу взят алгоритм предложенный мной вам .
Приступаю к описанию того , каким образом организовать очерёдность подхода к столу студентов . Т.е. ( своё объяснение ) заканчиваю с того с чего следует начать процедуру расселения 100 студентов из 400 .
Ну это просто - 400 карточек . С одной стороны нет ничего , что бы указывало какая цифра с 1 до 9 , или какое число с 10 до 400 написано на другой стороне карточки . Карточки лежат на столе . Каждый студент подходит берёт только одну и видит на ней номер указывающий на очерёдность подхода к столу .
Быть с самим собой , в согласии , должно быть самым естественным состоянием человека . Как быть в тех ситуациях , когда нужно выбрать 100 человек из 400 . Смогу ли я быть в согласии с самим собой , сам лично отдавая предпочтение тому или другому студенту ?
Ответ – однозначный нет . Привлекая сделать выбор самих студентов и вручая им в помощь сделать каждому из них правильный выбор , метод предложенный мной я не только обрекаю при этой процедуре ( выбор студентов ) на согласие за их выбор сам себя , я обрекаю на согласие с самим собой каждого из 400 студентов .