Отношение NP-Complete проблем к проблемам реального мира

Question

У меня есть приличное понимание NP Полные проблемы; это не проблема. Чего у меня нет, так это хорошего понимания того, где они появляются в «реальном» программировании. Некоторые (например, рюкзак и коммивояжер) очевидны, но другие, похоже, не связаны с «реальными» проблемами.

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

Существуют ли какие-либо ресурсы (онлайн или в печатном виде), которые специально связывают NP Complete с экземплярами реального мира?

Edit: Например, я работал над программой, которая пыталась разделить учащихся на группы по возрасту, классу и школе происхождения, что по сути является проблемой разбиения графиков. Мне потребовалось некоторое время, чтобы понять связь.

Answer 1

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

Answer 2

вот ссылка на вики: http://wapedia.mobi/en/List_of_NP-complete_problems Обратите внимание на это говорит

Этот список никоим образом не является исчерпывающим (существует более 3000 известных проблем с NP-завершением)

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

Теоретик должен попытаться понять / доказать проблему NP-Complete / Hard. Но у программиста нет на это времени. Ему нужен список.

Я прав?

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

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

PS: не забудьте опубликовать список, когда закончите: P

Answer 3

Обычно соединение, о котором вы говорите, должно быть извлечено с помощью так называемого сокращения , например, вы сводите 3-SAT к проблеме, с которой вы работаете, и затем вы можете сделайте вывод, что ваша проблема имеет ту же сложность.

Этот отрывок не является тривиальным, поскольку вам нужно доказать, что вы можете превратить каждый проблемный экземпляр l известной NP-Hard проблемы L в экземпляр c вашей проблемы C с использованием детерминированных полиномиальных алгоритмов.

Таким образом, кроме изучения основных корреляций распространенных NP-Hard проблем с использованием вашей памяти, нет никакого способа убедиться, что проблема похожа на другую NP-Hard без первого пытаясь угадать и затем доказать это, вы должны быть умным.

Answer 4

Для лучшего понимания интуиции книга « Руководство по разработке алгоритмов, второе издание » Скиены (выдержки из книг Google) просто великолепна.

1. Список в спину с проблемами (включая серьезные проблемы), что включить иллюстрацию и обсуждение (часто) с реальным миром Пример .
2. Охватывает как теоретическое и практическая сторона вещей, часто говорить о реальном коде.

Читайте исключения онлайн здесь (см. Некоторые примеры в главах 14): http://books.google.dk/books?id=7XUSn0IKQEgC&printsec=frontcover#v=onepage&q&f=false

Глава 16 (не в сети) обсуждает некоторые сложные проблемы, включая разбиение графа.