Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 15 ]  На страницу 1, 2  След.
Автор Сообщение
 Заголовок сообщения: Условие задачи P vs NP математического института Клэя
СообщениеДобавлено: 06 сен 2011, 19:15 
Не в сети
Начинающий
Зарегистрирован:
06 сен 2011, 19:13
Сообщений: 2
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Интересует задача P vs NP с точки зрения менеджера туризма. Т.е.: Как выглядит полное/подробное условие к задаче с сайта Математического Института Клэя? http://www.claymath.org/millennium/P_vs_NP/

Оригинал: Suppose that you are organizing housing accommodations for a group of four hundred university students. Space is limited and only one hundred of the students will receive places in the dormitory. To complicate matters, the Dean has provided you with a list of pairs of incompatible students, and requested that no pair from this list appear in your final choice.

Перевод: Предположим что вы организуете размещение четырехсот студентов университета в общежитии. Но общежитие не может вместить всех, и места в этом общежитии получат только сто из студентов. Чтобы усложнить задачу, декан выдал список пар несовместимых студентов и потребовал, чтобы ни одна пара из этого списка не оказалась в конечном списке.

Мне не понятно:

1. как выглядит список декана?
2. какая пропорция несовместимых студентов 50/50 к 400 или 100 студентам?
3. фамилии или цифры в списке декана?


Сейчас только догадываюсь, что:

* в прошлом - 400 студентов, 100 номеров, пропорция 50/50 несовместимых студентов;
* в будущем - 100 студентов, 100 номеров, несовместимые студенты есть, но по списку они проживают корректно и декан доволен.

Надеюсь на ваше понимание.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Условие задачи P vs NP математического института Клэя
СообщениеДобавлено: 07 сен 2011, 08:21 
Не в сети
Light & Truth
Зарегистрирован:
11 май 2011, 16:52
Сообщений: 4429
Cпасибо сказано: 38
Спасибо получено:
1115 раз в 923 сообщениях
Очков репутации: 409

Добавить очки репутацииУменьшить очки репутации
Список декана - это перечисление всех неупорядоченных пар несовместимых студентов.
Студент задается списком из его фамилии, имени, даты и места рождения, присвоенного ему № карточки социального страхования.
В списке декана 29517 несовместимых пар, причем некоторые студенты упомянуты в нескольких парах.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Условие задачи P vs NP математического института Клэя
СообщениеДобавлено: 07 сен 2011, 13:50 
Не в сети
Начинающий
Зарегистрирован:
06 сен 2011, 19:13
Сообщений: 2
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Задача с точки зрения менеджера отеля для конференций футурологического конгресса. (аналог http://www.claymath.org/millennium/P_vs_NP/)

Менеджер отеля ждет 400 гостей, все гости ученые - часть информатики, а часть математики, пропорция неизвестна. К моменту приезда ученых выяснилось, что в наличии есть только 50 двухспальных номеров и в отеле смогут разместиться только 100 ученых. Так уж вышло, что Футурологический конгресс из статистической сводки определил список несовместимых между собой ученых (список вида: 1/13, 4/56 ... 5/400; где цифра это идентификационный номер ученого, и где на одного ученого одна несовместимость). Необходимо быстро (за полиномиальное время) расселить гостей попарно и учесть пожелания конгресса о совместимости.

Дано:

- 400 гостей из которых только 100 гостей смогут разместиться в отеле;
- 50 номеров - в каждом номере по две постели;
- Список несовместимых гостей - в любой пропорции;

Задача: придумать как разместить всех гостей попарно в 50 номеров с учетом списка несовместимых пар за полиномиальное время.

PS: мои догадки: с точки зрения менеджера отеля:

в прошлом: 400 гостей, 50 номеров - заселены 0 постелей;
в настоящем: 400 гостей, 50 номеров - заселены 50 постелей;
в будущем: 100 гостей, 50 номеров - заселены 100 постелей.

PPS: Все критические замечания к условию задачи учитываются.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Условие задачи P vs NP математического института Клэя
СообщениеДобавлено: 03 дек 2011, 01:31 
Не в сети
Начинающий
Зарегистрирован:
03 дек 2011, 00:52
Сообщений: 3
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Как я доказал что NP=P .
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 проверка показала, да, действительно ответ был правильным, ну тут уж никуда не денешься, математика, как известно, наука точная.

Для чего это нужно, в конце концов?

Всё очень просто - это нужно для того, чтобы в сознании сформировалось осознание того, что каким бы не был сложным вопрос, на него всегда можно получить ответ, это, во-первых. А во-вторых, время задавания вопроса равно времени его получения. Т.е. задавая вопрос, сколько будет 4587*8315, я получаю ответ в процессе его задавания, для данных чисел он равен 3. Думать некогда, есть время только действовать. И сознание начинает действовать сразу же в процессе получения вопроса. Постепенно, в процессе практики, оно - сознание - прейдет к выводу, что оно в состоянии принимать правильные решения, невзирая на сложность поставленной задачи. Вот таким простым способом будем тренировать своё сознание, укреплять его, так сказать, в мысли, что оно быстрое и ответственное. Ответственное по тому факту, что решение задачи правильное.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Условие задачи P vs NP математического института Клэя
СообщениеДобавлено: 03 дек 2011, 01:37 
Не в сети
Начинающий
Зарегистрирован:
03 дек 2011, 00:52
Сообщений: 3
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Как я разместил студентов .
В начале хочу обратить ваше внимание на то , что 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 пар и мы тоже это видим .
Нам ни что и ни кто не мешает назвать пары цифр равных друг другу , назвать совместимыми друг с другом . И пары цифр не равных друг другу , не совместимых друг с другом . Позже мы поймём почему мы так сделали . Далее я привожу информацию данную Amicus Plato /. Адрес где она разместила эту информацию прилагается сразу же после её текста ( т.е. отрывка её текста размещённого здесь )
« Кстати, на сайте этого института дано уморительное описание этой проблемы!
http://www.claymath.org/millennium/P_vs_NP/
Не поленюсь даже и переведу. (Хотя за точность перевода ручаться не буду)
***
Предположим, вы организуете расселение четырехсот студентов университета. Однако (как всегда) общежитие не может вместить всех, и места в этом общежитии получат только сто из них. Чтобы усложнить вашу задачу, декан выдал вам список пар "несовместимых студентов" и потребовал, чтобы ни одна пара из этого списка не оказалась вместе!
Это пример того, что ученые называют NP-задачей, т.к. легко проверить, является ли определенный выбор ста студентов подходящим (т.е. ни одна пара из результирующего списка не оказалась в списке, выданном деканом), однако задача формирования такого списка с нуля кажется настолько трудной, что выполнить ее практически невозможно.
В самом деле, общее число путей выбора ста студентов из четырехсот кандидатов больше чем число атомов в нашей Вселенной! (прим. АР: неужели правда? С400100 — больше, чем число атомов Вселенной? Хотя что это я... Если всего-то до миллиарда можно считать больше 30 лет...)
Таким образом никакая цивилизация будущего не может даже надеяться на создание суперкомпьютера, способного решить эту задачу с помощью "грубой силы" )))), т.е. проверяя каждую возможную комбинацию 100 студентов из 400. Однако эта очевидная трудность может всего лишь отражать недостаток изобретательности вашего программиста ))))
Фактически, это одна из выдающихся проблем информатики — доказать существование или несуществование такого вопроса, ответ на который можно легкопроверить, но который требует невероятно долгого времени для своего решения любым прямым методом.
Задачи, аналогичные той, которую мы рассмотрели, точно кажутся именно такими! Но однако до сих пор никто не смог доказать, что хотя бы одна из них, на самом деле настолько сложна, как кажется! Т.е. что на самом деле нет ни одного возможного способа получить ответ с помощью компьютера. Стивен Кук и Леонид Левин сформулировали проблему Р (т.е. легко найти) vs NP (т.е. легко проверить) независимо друг от друга в 1971 г.
(Конец цитаты)

Так что если кто-то таки найдет доказательство равенства этих классов, смело сможет расселять студентов по общежитиям)))
А на самом деле, всё-таки, надо полагать, кроме огромного минуса в виде полного кризиса в области защиты данных, человечество получит и грандиозный плюс! Решать быстро задачи такого класса сложности — оооо, этим надо гордиться! Только вот что-то расправляться с этой проблемой никто не торопится...»
http://www.diary.ru/~Organon/p45930819.htm?oam#more1 - по этому адресу полный текст .

«список пар "несовместимых студентов" и потребовал, чтобы ни одна пара из этого списка не оказалась вместе!»
Мы имеем список пар несовместимых студентов их ровно 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;





Николай Иванович ШИРЯЕВ
.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Условие задачи P vs NP математического института Клэя
СообщениеДобавлено: 03 дек 2011, 01:43 
Не в сети
Начинающий
Зарегистрирован:
03 дек 2011, 00:52
Сообщений: 3
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Продолжение и всё по этой теме у меня здесь:http://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 студентов .

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Условие задачи P vs NP математического института Клэя
СообщениеДобавлено: 31 мар 2014, 19:54 
Не в сети
Оракул
Зарегистрирован:
03 июл 2013, 12:54
Сообщений: 895
Cпасибо сказано: 6
Спасибо получено:
40 раз в 35 сообщениях
Очков репутации: 2

Добавить очки репутацииУменьшить очки репутации
Бредятина! :hh:)
Без меня тут, что правда все свихнулись? :puzyr:)
Мне бы Ваши задачки решать радовался бы. :)
Задачки типа [math]N[/math] посетителей надо разместить на [math]M[/math] номеров. И каждый номер имеет [math]j[/math] мест.
Причём [math]n_{i}[/math] клиент имеет [math]k_{i}[/math] не совместимых партнёров.
Решается элементарно.
Это ещё в старые времена в трактире так размешали, чтоб не передрались друг с другом.
Это не первая задачка когда математики пытаются решить задачки которые весь народ спокойно решает сам. :)

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Условие задачи P vs NP математического института Клэя
СообщениеДобавлено: 31 мар 2014, 20:21 
Не в сети
Оракул
Зарегистрирован:
09 сен 2011, 12:29
Сообщений: 760
Cпасибо сказано: 16
Спасибо получено:
221 раз в 185 сообщениях
Очков репутации: 89

Добавить очки репутацииУменьшить очки репутации
Вот вариант нормальной формулировки:
Дана произвольная КНФ [math](y_{11}\vee...\vee y_{1k_1})\wedge...\wedge(y_{s1}\vee...\vee y_{sk_s})[/math] от [math]n[/math] булевых переменных [math]y_{ij}\in\{x_1,...,x_n\}[/math], надо определить за полиномиальное от [math]n[/math] время, существует ли набор значений переменных, подстановка которых дает истинное значение КНФ, или показать, что такого набора не существует.
А individ как всегда несет херню, в чем мы очередной раз убедились :O:

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Условие задачи P vs NP математического института Клэя
СообщениеДобавлено: 31 мар 2014, 21:12 
Не в сети
Оракул
Зарегистрирован:
03 июл 2013, 12:54
Сообщений: 895
Cпасибо сказано: 6
Спасибо получено:
40 раз в 35 сообщениях
Очков репутации: 2

Добавить очки репутацииУменьшить очки репутации
Sonic если такой умный - может решение приведёшь?
А потом мы все вместе посмеёмся!
Никак до них не дойдёт, что надо решать, а не пыль в глаза пускать!

Бредятина полная. Вместо того чтоб сказать придумай, чтоб очень быстро всех разместить пишет:"... за полиномиальное от [math]n[/math] время..."

Почти, что как по пословице: "Если не знаешь, что сказать - говори по французски!"

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Условие задачи P vs NP математического института Клэя
СообщениеДобавлено: 25 апр 2014, 09:51 
Не в сети
Начинающий
Зарегистрирован:
17 апр 2014, 14:13
Сообщений: 10
Cпасибо сказано: 0
Спасибо получено:
4 раз в 4 сообщениях
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Задача о размещении студентов - это так называемая задача Клика (Clique) в литературной обработке, хорошо известная NP-полная задача. Кстати, даже официальном сайте она сформулирована не совсем корректно. Очень существенно, что решение NP-полной задачи состоит не в том, чтобы найти список студентов, а в том, чтобы доказать, что такой список существует или что такой список не существует.
Sonic сформулировал еще одну NP-полную задачу - задачу Выполнимости. Собственно, это первая задача, у которой была доказана ее NP-полнота.
Остальные несут бред.

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему    На страницу 1, 2  След.  Страница 1 из 2 [ Сообщений: 15 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Задачи математического программирования

в форуме Исследование операций и Задачи оптимизации

HJey

19

892

23 ноя 2018, 10:54

Не понимаю условие задачи

в форуме Функциональный анализ, Топология и Дифференциальная геометрия

AAoAAoAAo

6

254

01 дек 2020, 23:55

Не понимаю условие задачи. Гироскоп

в форуме Механика

MariaVic

6

607

27 ноя 2016, 14:58

Условие задачи симплекс-метода

в форуме Исследование операций и Задачи оптимизации

Pragramer228

1

439

02 май 2014, 21:32

Не могу понять условие задачи

в форуме Теория вероятностей

adeptus7

0

242

17 май 2017, 11:22

Усложненное условие задачи о стрелках

в форуме Теория вероятностей

galachel

2

412

17 янв 2016, 20:54

Корректно ли условие задачи и ее решение?

в форуме Алгебра

liliya347347

9

178

11 дек 2023, 10:46

Условие задачи для решения симплекс методом

в форуме Исследование операций и Задачи оптимизации

Anastasia0195

0

384

12 май 2014, 02:39

Задача с математического турнира

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

zakharova-forum

3

257

11 июл 2020, 15:43

Определение математического ожидания

в форуме Теория вероятностей

K_A

5

276

01 мар 2018, 20:03


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 8


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved