Марк Доминус собрал несколько примеров сокращения за полиномиальное время от различных задач NP-hard до сопоставления с «регулярным выражением» . Предвидение проверок за полиномиальное время не является огромным скачком.
Как вы можете проиллюстрировать класс NP-complete студентам или друзьям в других областях, которые хотели понять недавнюю суету из-за работы Деолаликара?
np-hardness
big-list
Грег Бэкон
источник
источник
Некоторые «повседневные» проблемы, которые NP-сложны, правильно сформулированы:
Назначение университетских классов временным интервалам, чтобы минимизировать конфликты планирования.
Распределение гостей по местам так, чтобы друзья сидели за одним столом, а враги - нет.
Планирование поездки, чтобы посетить все туристические места в списке, чтобы минимизировать вождение.
источник
Проблема коммивояжера, по-видимому, доступна ... по крайней мере там, где я нахожусь, это, кажется, самая популярная проблема CS среди людей, не относящихся к CS. Я также нашел следующую иллюстрацию Vertex Cover довольно привлекательной, представленной моим инструктором по алгоритмам:
У вас есть дорожная сеть, и вы хотите, чтобы в случае, если в автомобиле не осталось топлива, на одном конце дороги была заправка.
Как планировщик города, вы хотите минимизировать расходы, построив наименьшее количество заправочных станций. По сути, это проблема покрытия вершин, и я нашел некоторый успех в указании на то, что, хотя вы не ожидаете найти оптимальное покрытие вершин за полиномиальное время, вы можете найти что-то, что находится за два раза за полиномиальное время, просто подбирая обе конечные точки максимального соответствия (ну, эта последняя деталь может быть опущена в зависимости от того, насколько интересна ваша аудитория - тем более, что алгоритм MM не совсем двухстрочный).
Что касается примера «скачка сложности» с небольшим изменением характера проблемы, я думаю, что разница между проверкой 2-цветности и 3-цветности является хорошим примером. При всей гласности, связанной с теоремой о четырех цветах, можно также указать, что проверить, можно ли правильно раскрасить карту только тремя цветами вместо четырех, хотя мы знаем, что она всегда может быть окрашена четырьмя цветами. Довольно много людей находят это довольно поразительным.
Еще одна довольно естественная ситуация - проблема тупикового восстановления в операционных системах. Это моделируется NP-полной проблемой набора вершин обратной связи - наименьшего числа вершин, удаление которых делает граф ациклическим - и я нахожу это также замечательным примером (и объясняется далее в той статье в Википедии).
источник
Я думаю, что параллельная парковка NP-сложна.
На самом деле, более общая проблема поиска кратчайшего пути с ограниченной кривизной, который переводит многоугольный объект из исходного положения в конечное положение в многоугольной среде, является NP-трудной. Доказательство можно найти здесь - http://portal.acm.org/citation.cfm?id=298976
источник
Рюкзак легко понять, особенно для тех, кто имел дело с небольшим чемоданом ... хороший пример, если они знают динамическое программирование.
Другим забавным (практически идентичным) является 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-полным).
источник
Построение кроссворда - NP-Complete: учитывая набор ответов, постарайтесь поместить их в сетку.
источник
Я создал веб-сайт Tagxedo, http://www.tagxedo.com , генератор облаков слов, который подбирает слова (в зависимости от их частоты) в форму. Результаты очень симпатичные, но проблема в том, что проблема NP-сложна (проблема упаковки).
Интересно, что многие NP-сложные задачи имеют «легкие» приближения. Tagxedo, кажется, делает почти идеальную работу во многих случаях. Это приводит к интересной дискуссии о практическом значении P против NP и теме аппроксимации.
источник
Один из моих друзей провел творческий отпуск, наблюдая за игрой в бейсбол на каждом стадионе высшей лиги в Северной Америке. Без полета. (Он не совсем преуспел; три стадиона строились в этом году.)
источник
Благодаря успеху таких компаний, как Uber и Lyft, многие люди имеют очень доступный прямой опыт решения проблем, связанных с NP.
Эта проблема (если ее перефразировать) связана с NPC, и я думаю, что люди в какой-то момент задались вопросом, как Uber решает объединить водителей и пассажиров.
источник
Я обычно использую SAT в качестве примера. Я говорю что-то вроде «всевозможные проблемы, которые возникают постоянно, могут быть переписаны как поиск истинного назначения для большой логической формулы. Вопрос P против NP заключается в том, существует ли принципиально более простой способ решения этой логической формулы, чем просто Испытывая все возможности. До сих пор никто не смог ни найти пути, ни доказать, что нет легкого выхода ».
источник
Np-полная проблема, такая как Sudoku (на nxn sqaure), похожа на универсальный инструмент, который позволяет нам эффективно решать все проблемы, которые имеют эффективно проверяемые решения. Единственное требование - иметь эффективный метод решения судоку.
источник
Надеюсь это поможет!
источник
Причудливо доступным примером является краткая презентация Марка Доминуса (см. Соответствующий пост в блоге ) под названием «Моя любимая NP-полная проблема», где на изображении ниже показана изюминка обзора точного покрытия с тремя наборами .
Названия в видео серии включают
Ясное намерение состояло в том, чтобы каждое видео содержало три эпизода, все на общую тему, взятые из совокупности тем, представляющих интерес для маленьких детей.
Странной уткой в сериале было видео «Цветы, бананы и… волосы».
источник
Особенно при рассмотрении проблемы с рюкзаком позже, эта NP-полная проблема может подойти:
Угадайка чисел, где ты можешь угадать только одно число, пока не получишь правильное.
источник