Ежедневные встречи с NP-полными проблемами

34

Марк Доминус собрал несколько примеров сокращения за полиномиальное время от различных задач NP-hard до сопоставления с «регулярным выражением» . Предвидение проверок за полиномиальное время не является огромным скачком.

Как вы можете проиллюстрировать класс NP-complete студентам или друзьям в других областях, которые хотели понять недавнюю суету из-за работы Деолаликара?

Грег Бэкон
источник

Ответы:

24

Мой любимый пример для использования с друзьями не из CS:

Авраам, А. Блюм, Сандхольм. Клиринговые алгоритмы для бартерных биржевых рынков: возможность обмена почками по всей стране. EC07.

Биржевые рынки почек - это, по сути, ограниченная форма покрытия цикла. Мне нравится этот пример, потому что а) легко объяснить суть (если вы пропустите некоторые технические детали) и б) это один из немногих известных мне случаев, когда лучшие алгоритмы могут буквально спасать жизни!

Мой второй любимый пример - проблема с больницами и жильцами (она же проблема с поступлением в колледж). Каждая больница ранжирует всех резидентов (выпускников медицинских вузов), а резиденты ранжируют больницы. В каждой больнице есть определенное количество мест. Отсюда проблема стабильного сопоставления и может быть решена за полиномиальное время.

Но на самом деле пары могут войти в систему (да, действительно, система ) вместе, так что система, например, не будет разделять супружеские пары, которые обе претендуют на вид на жительство. Добавление пар делает задачу NP-полной. Помимо того, что это легко объяснить, это наглядно демонстрирует, как введение соединений на большие расстояния может вызвать NP-полноту.

Джошуа Грохов
источник
1
Отличный пример! Дэвид Мэнлоу много работал над такими проблемами (как обмен, так и сопоставление); системы используются в Великобритании и Венгрии. dcs.gla.ac.uk/~davidm/publications.html Насколько мне известно, эти подходы превосходят алгоритмы NRMP, и алгоритм Эрик МакДермид с 3/2-приближением является наиболее известным. dx.doi.org/10.1007/978-3-642-02927-1_57
Саламон
13

Некоторые «повседневные» проблемы, которые NP-сложны, правильно сформулированы:

  • Назначение университетских классов временным интервалам, чтобы минимизировать конфликты планирования.

  • Распределение гостей по местам так, чтобы друзья сидели за одним столом, а враги - нет.

  • Планирование поездки, чтобы посетить все туристические места в списке, чтобы минимизировать вождение.

Аарон Рот
источник
12

Проблема коммивояжера, по-видимому, доступна ... по крайней мере там, где я нахожусь, это, кажется, самая популярная проблема CS среди людей, не относящихся к CS. Я также нашел следующую иллюстрацию Vertex Cover довольно привлекательной, представленной моим инструктором по алгоритмам:

У вас есть дорожная сеть, и вы хотите, чтобы в случае, если в автомобиле не осталось топлива, на одном конце дороги была заправка.

Как планировщик города, вы хотите минимизировать расходы, построив наименьшее количество заправочных станций. По сути, это проблема покрытия вершин, и я нашел некоторый успех в указании на то, что, хотя вы не ожидаете найти оптимальное покрытие вершин за полиномиальное время, вы можете найти что-то, что находится за два раза за полиномиальное время, просто подбирая обе конечные точки максимального соответствия (ну, эта последняя деталь может быть опущена в зависимости от того, насколько интересна ваша аудитория - тем более, что алгоритм MM не совсем двухстрочный).

Что касается примера «скачка сложности» с небольшим изменением характера проблемы, я думаю, что разница между проверкой 2-цветности и 3-цветности является хорошим примером. При всей гласности, связанной с теоремой о четырех цветах, можно также указать, что проверить, можно ли правильно раскрасить карту только тремя цветами вместо четырех, хотя мы знаем, что она всегда может быть окрашена четырьмя цветами. Довольно много людей находят это довольно поразительным.

Еще одна довольно естественная ситуация - проблема тупикового восстановления в операционных системах. Это моделируется NP-полной проблемой набора вершин обратной связи - наименьшего числа вершин, удаление которых делает граф ациклическим - и я нахожу это также замечательным примером (и объясняется далее в той статье в Википедии).

Neeldhara
источник
3
Максимальное согласование достаточно для двух приближений, что гораздо проще вычислить и объяснить.
Уоррен Шуди
1
@Warren: Спасибо, что указали на это, конечно, вы совершенно правы!
Нилдхара
8

Я думаю, что параллельная парковка NP-сложна.

На самом деле, более общая проблема поиска кратчайшего пути с ограниченной кривизной, который переводит многоугольный объект из исходного положения в конечное положение в многоугольной среде, является NP-трудной. Доказательство можно найти здесь - http://portal.acm.org/citation.cfm?id=298976

Винаяк Патхак
источник
7

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

Другим забавным (практически идентичным) является Subset-sum, потому что он также имеет хорошую физическую интерпретацию: представьте, что числа представляют собой расстояния равных точечных масс на идеальной (безмассовой) линейке с точкой опоры в начале координат. Сумма подмножества говорит: существует ли непустое подмножество, так что линейка останется сбалансированной? (т.е. такой, что центр тяжести является опорным пунктом для правителя?)

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

Если у них больше предыстории, неплохо бы вырастить проблемы, отбросив ограничения. Например, начиная с задачи с максимальным потоком, превращая ее в линейную программу и делая ее целочисленной программой. (Отличным, конечно же, является MAX-CUT, поскольку для людей с большим опытом работы вы также можете открыть UGC; я касаюсь некоторых из них в ответе МО https://mathoverflow.net/questions/33036/is-quadratic-programming -still-np-hard-if-you-have-bounds-and-a-feasible-point / 33048 # 33048. ) Также есть изящные вещи, такие как проблемы, кажущиеся схожими, которые имеют существенно различную сложность (путь Эйлера (ребро) является линейным время гамильтонова (вершинного) пути является NP-полным).

оборота матус
источник
7
Мне нравится следующая версия Subset Sum: вам дают 10 фунтов на покупку закусок в магазине. Можете ли вы найти точно правильную комбинацию покупок, чтобы не осталось денег?
Андрас Саламон
6

Построение кроссворда - NP-Complete: учитывая набор ответов, постарайтесь поместить их в сетку.

Арьябхата
источник
5

Я создал веб-сайт Tagxedo, http://www.tagxedo.com , генератор облаков слов, который подбирает слова (в зависимости от их частоты) в форму. Результаты очень симпатичные, но проблема в том, что проблема NP-сложна (проблема упаковки).

Интересно, что многие NP-сложные задачи имеют «легкие» приближения. Tagxedo, кажется, делает почти идеальную работу во многих случаях. Это приводит к интересной дискуссии о практическом значении P против NP и теме аппроксимации.

Харди Леунг
источник
4

Один из моих друзей провел творческий отпуск, наблюдая за игрой в бейсбол на каждом стадионе высшей лиги в Северной Америке. Без полета. (Он не совсем преуспел; три стадиона строились в этом году.)

Jeffε
источник
да, но пытался ли он минимизировать потребление газа? :)
Суреш Венкат
Даже найти выполнимый график было непросто, потому что стадионы открыты не каждый день (гамильтонов цикл с временными окнами).
Джефф
4

Благодаря успеху таких компаний, как Uber и Lyft, многие люди имеют очень доступный прямой опыт решения проблем, связанных с NP.

Учитывая совокупность водителей и список людей, которые хотят быть поднятыми в разное время, каково наиболее эффективное распределение пассажиров водителям?

Эта проблема (если ее перефразировать) связана с NPC, и я думаю, что люди в какой-то момент задались вопросом, как Uber решает объединить водителей и пассажиров.

Стелла Бидерман
источник
3

Я обычно использую SAT в качестве примера. Я говорю что-то вроде «всевозможные проблемы, которые возникают постоянно, могут быть переписаны как поиск истинного назначения для большой логической формулы. Вопрос P против NP заключается в том, существует ли принципиально более простой способ решения этой логической формулы, чем просто Испытывая все возможности. До сих пор никто не смог ни найти пути, ни доказать, что нет легкого выхода ».

Александр Пассос
источник
2
Я не уверен, сколько людей сталкиваются с этим каждый день.
Дэйв Кларк
3

Np-полная проблема, такая как Sudoku (на nxn sqaure), похожа на универсальный инструмент, который позволяет нам эффективно решать все проблемы, которые имеют эффективно проверяемые решения. Единственное требование - иметь эффективный метод решения судоку.

Мухаммед Аль-Туркистани
источник
2

Nп

NпJмNппJКNп-полный в этой ситуации. Заметьте, что это не обязательно должны быть блоки, если мы предполагаем, что они не могут опрокинуться. Это могут быть стопки бумаг, ящиков или тарелок.

Надеюсь это поможет!

PageWizard
источник
2

Причудливо доступным примером является краткая презентация Марка Доминуса (см. Соответствующий пост в блоге ) под названием «Моя любимая NP-полная проблема», где на изображении ниже показана изюминка обзора точного покрытия с тремя наборами .

Названия в видео серии включают

  • Танцы, музыка и книги
  • Руки, уши и ноги
  • Проснись с Элмо (о сне, одевании и чистке зубов)
  • Люди в вашем районе (про пожарных, спасателей и медсестер)

Ясное намерение состояло в том, чтобы каждое видео содержало три эпизода, все на общую тему, взятые из совокупности тем, представляющих интерес для маленьких детей.

Странной уткой в ​​сериале было видео «Цветы, бананы и… волосы».

Цветы, бананы и… волосы.

Грег Бэкон
источник
0

Особенно при рассмотрении проблемы с рюкзаком позже, эта NP-полная проблема может подойти:

Угадайка чисел, где ты можешь угадать только одно число, пока не получишь правильное.

Sudix
источник