Простыми словами
В конце прошлой записи мы вплотную подошли к проблеме равенства классов сложности P и NP. Сформулировать ее можно следующим образом:

Если правильность ответа на какой-либо вопрос можно проверить за полиномиальное время, то верно ли, что этот ответ возможно так же быстро найти (т.е. за полиномиальное время и используя полиномиальную память)?

читать дальше

@темы: Алгоритмы, Искусственный интеллект, Поп-математика, Amicus Plato

Комментарии
28.07.2008 в 22:38

Во всем мне хочется дойти до самой сути... (с)
Amicus Plato
Большое спасибо за такой чудесный цикл статей!!!
Это такой огромный труд!
(может тебе это где-нибудь издать? В каком-нибудь научном или научно-популярном издании. Потому что аналогов этому нет и не будет)
29.07.2008 в 10:07

Простыми словами
Sensile
да ну, брось! ))))
это же почти всё компиляция известных фактов! ))))
моих заслуг тут практически никаких)
А вообще: спасибо тебе большое! :red: :red: :red:
07.08.2008 в 15:04

великолепные статьи
07.08.2008 в 15:29

Простыми словами
Гость
большое спасибо. )
23.10.2008 в 17:21

Задача клики.

clique-problem.narod.ru
clique-problem.narod.ru/clique.pdf

Алгоритм полиномиальный.
23.10.2008 в 19:10

Простыми словами
Гость
спасибо за ссылки!
06.11.2008 в 23:56

Великолепная "компиляция"!

P.S.

"Стивен Кук и Леонид Левин сформулировали проблему Р (т.е. легко найти) vs NP (т.е. легко проверить) независимо друг от друга в 1971 г."

Кук - 1971
Левин (независимо) - 1973
Карп (1972) - предположил символы P и NP

Интересно: www.timescube.com
07.11.2008 в 15:48

Простыми словами
Гость
спасибо за поправки.

Вы бы подписывались как-то, если не сложно, а то даже не совсем понятно, вы один человек, или все "гости" здесь разные.
07.11.2008 в 15:51

Простыми словами
Интересно: www.timescube.com
Действительно, интересно! Спасибо!
Sensile, погляди на ссылку!
07.11.2008 в 16:42

Во всем мне хочется дойти до самой сути... (с)
Я что-то не пойму, что там такое(((
17.11.2008 в 00:17

А вот интересно, если скажем комбинаторно решена задача о неупорядоченных разбиениях. Имеет ли это какое-то отношение к P=NP.
14.05.2009 в 22:35

Мысль изреченная есть ложь.
Amicus Plato
Интересно, институт Клэя хочет получить решение проблемы Кука или задачи о расселении, как Вы думаете?
15.01.2010 в 23:58

Если правильность ответа на какой-либо вопрос можно проверить за полиномиальное время, то верно ли, что этот ответ возможно так же быстро найти (т.е. за полиномиальное время и используя полиномиальную память)? Это и есть формулировка проблемы Кука? Похоже, что нет.
Доказательство.
Богданов-Бельский на своей картине "Устный счёт" привёл выражение (10^2+11^2+12^2+13^2+14^2)/365, величину которого ученики церковно-приходской школы должны вычислить в уме.
Решение.
1. Так как найти значение выражения предлагается найти ученикам ЦПШ, да ещё и устно, уместно предположить, что оно целое.
2. Числитель заведомо больше 365=365х1 и заведомо меньше 1095=365х3.
Следовательно, ответ есть 2. Время счёта - менее 5 секунд.
Уверен, что проверить его быстрее нельзя.
Что, "проблема" решена?
Так какова же правильная формулировка проблемы Кука?.
03.11.2011 в 21:14

Сб, 23/04/2011 - 10:16 — С.А.Пн, 25/04/2011 - 09:25 — Н.И.Ширяев Проверка P в NP.
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
и дальнейшее её развитие.
04.11.2011 в 15:30

Продолжение .
Я не хочу здесь публиковать полностью список с результатами действия подхода остальных студентов , не в этом как говорится суть .Хочу лишь только сказать о том , что тот студент у которого одна из карточек которую он возьмёт окажется с цифрой 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 студентов .