Всем привет!

Время идет, квантовый мираж все яснее трансформируется в реальность, а доказательство равенства P и NP классов естественно, как бесконечность вселенной, т.к. с точки зрения космоса полиномиальное время безгранично.

Все помнят, что такое движущая сила человечества. Верно?

Хочу написать этот топик с задачей, для того, что бы он был на хабре до момента разрешения спора о равенстве классов.

Задача с точки зрения менеджера отеля для конференций футурологического конгресса. (аналог 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: Все критические замечания к условию задачи учитываются.


Сообщение отредактировал malto - 7.9.2011, 14:43