P равно NP, описание легко
В официальной ссылке проблемы P=NP на странице ниже:
P=NP Проблема Официальное описание
упоминается проблема организации жилья для группы из четырехсот студентов университета, где вместимость общежития составляет не более 100, а также декан предоставил список пар "несовместимых" студентов, то есть они могут не должны быть размещены вместе. Проблема также гласит, что создание такого списка с нуля было бы трудно / трудно. Но я немного подумал и нашел следующее решение:
Мы рассчитываем точное количество возможных пар, что можно сделать следующим образом:
Сначала мы выбираем 100 учеников из 400 доступных учеников. = (400 C100) способов.
Затем мы выбираем 2 учеников из каждого набора из 100 учеников по 100 C2 способами.
Затем для каждого набора он "добавляется" в окончательный набор результатов, если эта пара не существует в паре несовместимого декана.
Я знаю, что этот процесс составления списка займет много времени, так как сам список очень длинный. Но если мы рассмотрим 1-ю комбинацию из 100 учеников из 400 учеников ради УДАЧИ для немногих счастливчиков (я имею в виду, что это своего рода розыгрыш, и в итоге будет выбран только первый комплект из 100 учеников), тогда это будет легкая проблема в целом!
В любом случае, мы можем "сказать" в этой задаче, что набор решений существует или нет, как мы можем прямо сказать, возможны ли какие-либо пары, посмотрев список несовместимых студентов декана, поскольку все эти и только все те не должны быть в наборе результатов, так если есть 50 таких пар, это означает, что есть 100 несовместимых учеников, и мы можем выбрать 1-е 50 из этого списка и другие 50 из оставшихся 350 учеников? Это не кажется "трудным" как проблема 3SAT, где достаточно просто сказать, что решение существует. (Как и в этом случае, общее количество комбинаций составляет 400 C100 * [ 100 C2 - количество пар, которые есть в выбранном списке, а также в списке декана]
(Это также можно записать как 400 C100 * [ 100 C2 пары MINUS в списке декана], где MINUS - операция в терминологии базы данных.
Пожалуйста, пролите немного света на мои исследования, и если я прав или нет?
Спасибо
1 ответ
Я получил ответ в одном из комментариев к вопросу ниже:
Math Stack Exchange тот же вопрос темы
Общежитие - это не общежитие на 50 коек, а общежитие на 100 коек, и это не тот случай, когда 2 человека могут спать в одной кровати, и несовместимые студенты не могут находиться на одной кровати, но все же оставаться в общежитии на отдельных кроватях.